import java.util.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {

    Random rnd = new Random();

    long modMul(long a, long b, long mod) {
        long ans = 0;
        while (b > 0) {
            if ((b & 1) != 0) {
                ans += a;
                ans %= mod;
            }
            b >>= 1;
            a += a;
            a %= mod;
        }
        return ans;
    }

    long gcd(long a, long b) {
        while (b != 0) {
            a %= b;
            long temp = a;
            a = b;
            b = temp;
        }
        return a;
    }

    boolean rho = true;

    void factorize(long n, ArrayList<Long> result) {
        if (!rho) {
            int nc = (int)n;
            for (int i = 2; i * i <= nc; i++) {
                while (nc % i == 0) {
                    result.add((long)i);
                    nc /= i;
                }
            }
        } else {
            if (BigInteger.valueOf(n).isProbablePrime(20)) {
                result.add(n);
            } else {
                pollardRho(n, result);
            }
        }
    }

    void pollardRho(long n, ArrayList<Long> result) {
        while (true) {
            long x = rnd.nextLong() % n;
            if (x < 0) {
                x += n;
            }
            long y = x;
            for (int i = 2; i <= (1 << 10); i++) {
                //x = modMul(x, x, n) - 1;
                x = (x * x - 1) % n;
                if (x < 0) {
                    x += n;
                }
                long val = y - x;
                if (val < 0) {
                    val += n;
                }
                long d = gcd(val, n);
                if (d != 1 && d != n) {
                    factorize(d, result);
                    factorize(n / d, result);
                    return;
                }
                if ((i & (i - 1)) == 0) {
                    y = x;
                }
            }
        }
    }

    public void solve() throws Exception {
        int cnt = 100;
        long first = 30000;
        long[] primes = new long[cnt];
        for (int i = 0, j = 0; j < cnt; i++) {
            if (BigInteger.valueOf(first + i).isProbablePrime(100)) {
                primes[j++] = first + i;
            }
        }
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            long n = primes[rnd.nextInt(cnt)] * primes[rnd.nextInt(cnt)];
            ArrayList<Long> result = new ArrayList<>();
            factorize(n, result);
            if (i % 1000 == 0) {
                out.println(i);
                out.flush();
            }
        }
        out.println(System.nanoTime() - start);
    }

    static Throwable uncaught;

    BufferedReader in;
    FastScanner sc;
    PrintWriter out;

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            sc = new FastScanner(in);
            solve();
        } catch (Throwable uncaught) {
            Solution.uncaught = uncaught;
        } finally {
            out.close();
        }
    }

    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        if (Solution.uncaught != null) {
            throw Solution.uncaught;
        }
    }

}

class FastScanner {

    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

}