Problem 3
篩も懐かしいねー
#include <iostream> #include <cmath> using namespace std; #define NUM 600851475143 int main(int argc, char ** argv) { unsigned int size = (unsigned int)ceil(sqrt((double)NUM)); // 篩の大きさ bool *t_prime = new bool [size]; // 素数テーブル memset(t_prime, true, size); // 篩にかける t_prime[0] = t_prime[1] = false; for (unsigned int i = 2; i < size; i++) { if (t_prime[i]) { for (unsigned int j = i+i; j < size; j+=i) { t_prime[j] = false; } } } // 素因数分解 long long d = NUM; // もとの値 int pf; // 素因数 for (unsigned int i = 2; i < size; i++) { if (t_prime[i]) { while (1) { if (d%i == 0) { d /= i; pf = i; } else { break; } } } } // 出力 cout << pf << endl; return 0; }