project euler #003について

Question

project eulerの3問目に以下のようなものがありました。

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

以下のコードは自力でやってみたものです。

#include <stdio.h>

//judge関数の定義//
int judge(long long x){
    
    int y = 0;
    
    for (long long j=2; j<x; j++) {
        if (x%j == 0) {
            y = 1;
            break;
        }
    }

    return y;
}


int main(void){
    
    long long i, j;
    long long num;
    long long maxprime = 1;
    
    printf("整数を入力してください。\n");
    scanf("%lld", &num);

    for (i=1; i<=num; i++) {
            if (num%i == 0) {
                j = judge(i);
        
                if (j == 0) {
                    maxprime = i;
                }
            }
    }

    printf("最大の素因数は%lldです。\n", maxprime);

    return 0;
}

問題を解くにあたり考えたアルゴリズムは、
値を入力させる→約数を見つける→約数内で素数を見つける
というものです。
しかし、このコードでビルドしたところnumが比較的小さい値の時はしっかりと最大の素因数が求まるのですが、600851475143などの大きい値の時、何も起こらなくなってしまいます。初心者なのでコードに一貫性がないのは重々承知です。どなたか原因を教えていただけると幸いです。

Answer 1

大きい数字のとき何も起こらない(ように見える)のは、処理に時間がかかり過ぎているからです。
このアルゴリズムの場合、例えば1000を入力したときに0.001秒で結果が出るとすると、12桁の数字を入力した場合、10万秒、つまり1日以上かかります。

抜本的にアルゴリズムを変えてみます。
nを2,3,...で割っていったとき、最初にpで割り切れたとします。
そうしたら、次はn/pをp,p+1,...で割っていきます。
(nはp未満の素数では割り切れませんから、p以上で探索すれば十分です。)
n/pがp以上の数qで割り切れたとき、pからqまでの間にn/pを割り切ることのできる数が存在しなければ、qは素数です。(qはp未満の数で割り切れず、qが合成数であればp以上q未満の約数を必ずもつから)
その次はn/pqをq,q+1,...で割っていきます。そのようにして、最後にn/pq...を割り切ることのできた数(n/pq...自身)が、最大の素因数です。
コードに書き起こすと、以下のようになります(一部最適化済み)。

long long maxprime = 1;
for( long long p = 2; p <= n / p; p++ ){
    while( n % p == 0 ){
        maxprime = p;
        n /= p;
    }
}
if( n > 1 ){
    maxprime = n;
}

なぜこのコードで正しく動作するのかはゆっくり考えてみてください。

Comments

[engawa]

だいぶ自信のあったコードだったので、処理に1日以上もかかると聞き驚きを隠せませんが...
高速に処理するにはどのようなアルゴリズムが適当か、教えてくださったコードを眺めてじっくり考えたいと思います。まだ未熟ですが回答者様のように、シンプルで整ったコードを書けるよう勉強を続けたいと思います。回答ありがとうございました。

追記：お教えくださったコードの意味がやっと理解できました。ちっちゃい素因数を削っていくと自然と大きいのが出てくるということですね。大変勉強になりました!

Answer 2

こんにちは。

単純に計算に時間が掛かっているだけのようです。
タスクマネージャでみると、CPUの消費%は安定してます。
こんなに大きな数字なので、高速なアルゴリズムを使わないと厳しいということです。

素数かどうか判定するアルゴリズムがいろいろありますので、工夫されてみてください。

Comments

[engawa]

処理速度についても考慮したアルゴリズムを考えることも必要なのですね。素数判定アルゴリズムのリンクも参考にして、いろいろ試行錯誤したいと思います。お返事ありがとうございました。