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