Problem 3

13195 の素因数は 5、7、13、29 である。 600851475143 の素因数のうち最大のものを求めよ。

Problem 3 - PukiWiki

以下のステップでプログラムを作成。
target:素因数分解の対象となる数(600851475143)、divider:割る数、loop_max:dividerの上限、とする。

1. dividerに2をセット、loop_maxはtargetの平方根(に一番近い整数)にセット
2. targetをdividerで割って割り切れた場合、以下を実行
   1. targetをdividerで割った数をtargetに再代入
   2. loop_maxを再度targetの平方根(一番近い整数)にセット
3. 割り切れなかった場合はdividerをインクリメント
4. dividerがloop_maxと等しくなったときにtargetに格納されている整数を答えとする

#include <stdio.h>
#include <math.h>

#define TARGET_VALUE 600851475143LL

void problem003()
{
    int ans;
    int divider;
    long long int target = TARGET_VALUE;
    double loop_max;

    /* solve this problem here */
    divider = 2;
    loop_max = floor(sqrt(target));
    while (divider <= loop_max) {
        if (target % divider == 0) {
            target /= divider;
            loop_max = floor(sqrt(target));
        } else {
            divider++;
        }
    }

    ans = (int)target;

    printf("%s: answer = %d\n", __FUNCTION__, ans);
}

int main(int argc, char* argv[]) 
{
    problem003();
    return 0;
}

実行結果

$ ./problem003
problem003: answer = 6857

dividerの素数判定が必要かと思ったがそれを作っているより総当たりした方がいろんな意味で速かった。