// Eratosthenes (Java).
public class EratosthenesJ {
    private static final int MAX_ARRAY = 10000;

    public static void main(final String[] args) {
        final long start = System.nanoTime();
        final int maxprime = Integer.parseInt(args[0]);
        final java.util.HashMap<String, String> arr = new java.util.HashMap<String, String>(MAX_ARRAY);
        for (int base = 2; maxprime >= base; base += MAX_ARRAY) {
            final int arraysize = (MAX_ARRAY < maxprime - base + 1) ? MAX_ARRAY : maxprime - base + 1;
            arr.clear();
            for (int i = 2; (base + arraysize) / 2 > i; i++) {
                int k;
                if (base <= i)
                    k = i * i;
                else if (0 != base % i)
                    k = (base / i + 1) * i;
                else
                    k = base;
                for (; base + arraysize > k; k += i)
                    arr.put(Integer.toString(k - base), "");
            }
            final StringBuilder rs = new StringBuilder();
            for (int i = 0; arraysize > i; i++)
                if (!arr.containsKey(Integer.toString(i)))
                    rs.append(base + i).append(System.getProperty("line.separator"));
            System.out.print(rs.toString());
        }
        System.err.printf("%gsec.\n", (System.nanoTime() - start) / 1000000000.);
    }
}