UVa 10392 Factoring Large Number

題意：質因數分解

想法：
　　因為題目說1000000以上的質因數最多只有1個，因此我們質數表只要建到1000000即可，建表時可以跳過2和3的倍數比較快速。

	#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;
	}

view raw [UVa] 10392 Factoring Large Numbers.cpp hosted with ❤ by GitHub