質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.20%

project euler #003について

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 786

engawa

score 31

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などの大きい値の時、何も起こらなくなってしまいます。初心者なのでコードに一貫性がないのは重々承知です。どなたか原因を教えていただけると幸いです。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

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


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/14 22:40 編集

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

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

    キャンセル

+1

こんにちは。

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/14 22:23

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.20%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる