[UVa] 10392 Factoring Large Numbers.cpp

#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
    int prime[80000];
    int nOfprime = 2;
    prime[0] = 2;
    prime[1] = 3;
    for (int i = 5, gap = 2; i <= 1000000; i += gap, gap = 6-gap){
        int sqrt_i = sqrt(i);
        bool isPrime = 1;
        for (int j = 1; prime[j] < sqrt_i; j++){
            if (i % prime[j] == 0){
                isPrime = 0;
                break;
            }
        }
        if (isPrime)
            prime[nOfprime++] = i;
    }

    long long int N;
    while (scanf("%lld",&N)){
        if (N < 0) break;

        for (int i = 0; i < nOfprime; i++){
            while (N % prime[i] == 0){
                printf("    %d\n",prime[i]);
                N /= prime[i];
            }
            if (N == 1) break;
        }
        if (N != 1) printf("    %lld\n",N);
        printf("\n");
    }
    return 0;
}