import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.io.OutputStream; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.math.BigDecimal; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(1, in, out); out.close(); } static class Task { public void solve(int testNumber, InputReader in, PrintWriter out) { long N = in.nextLong(); int[] primses = sieveEratosthenes(1000000); long res=N; if(N%2==0) res=N/2; if(N%4==0) res=4; for(int i=1; i> 5] |= 1 << (i & 31); for (int j = 0; j < sup; j += tp) { for (int i = 0; i < tp && i + j < sup; i++) { isnp[j + i] |= ptn[i]; } } } // 3,5,7 // 2x+3=n int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 }; int h = n / 2; for (int i = 0; i < sup; i++) { for (int j = ~isnp[i]; j != 0; j &= j - 1) { int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27]; int p = 2 * pp + 3; if (p > n) break; ret[pos++] = p; if ((long) p * p > n) continue; for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q; } } return Arrays.copyOf(ret, pos); } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } } }