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

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

ただいまの
回答率

88.91%

n以下の素数をreturnするコードが遅いので改善したいです。

解決済

回答 3

投稿 編集

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

alizona

score 17

leet codeというウェブサービスを使って、問題を解いてるのですが、"Time Limit Exceeded"という実行結果が出ます。

どのように改善すれば良いでしょうか?

プログラムの要件は、
引数nより小さくて、負の数値でない素数の数をリターンする。
です。

よろしくお願いします。

class Solution {
public:
    int countPrimes(int n) {
        //nより小さくて、負の数値でない素数の数をリターンする。



        int count=0;

        bool isSosu;
        for(int m=2;m<n;m++){

            isSosu=true;
            for(int i=2;i<m;i++){

                if(m%i==0 && m!=i) //2以上で、同じ数字以外で割り切れた時は素数ではない
                    isSosu=false;

            }

            if(isSosu)
                count++;
        } 
        return count;
    }
};
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

+3

for(int i=2;i<m;i++){と書いた限り、im未満なので、&& m!=iという条件判断は無駄です。

他には、
・iは、m未満じゃなくて「mの平方根未満」で十分
・調べる対象もfor(int m=2;m<n;m++){のような2以上n未満全整数じゃなくて「2と、n未満の奇数」だけで十分
・そうするとiも奇数だけで十分

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2020/07/12 15:13

    教えていただいた3点を守ったところ、動くようになりました。ありがとうございました。

    キャンセル

  • 2020/07/12 15:14 編集

    if(n>2) //3以上の時は、2が奇数だから+1する
    count++;

    bool isSosu;
    for(int m=3;m<n;m=m+2){ //対象は3以上の偶数は素数ではない

    isSosu=true;
    for(int i=3;i<=sqrt(m);i=i+2){ //偶数はないから2で割る必要ない

    if(m%i==0){
    isSosu=false;
    i=m;//すでに素数でないことが見つかったので、loopから抜ける
    }
    }
    if(isSosu)
    count++;

    キャンセル

+1

素数の発掘は、効率の良いアルゴリズムがいくつかあるので、調査してみると良いですよ。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2020/07/12 14:14

    ありがとうございました。

    キャンセル

+1

例えば、「同じ数字以外で割り切れた時は素数ではない」の判断をする前に、「1桁の素数(2,3,5,7)で割り切れる数は素数でない」という条件で if(m%i==0 && m!=i) の判断をする回数を減らすと、速度が上がると思います。

使う素数の数を増やす(例えば2,3,5,7,11,13,17,19)と割り切れるかどうかの判断をする時間が伸びますが、if(m%i==0 && m!=i) の判断をする回数が減りますから、nが大きい時には使う素数の数をあるていど大きくしたほうが演算時間が短くなります。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2020/07/12 14:16

    "nが大きい時には使う素数の数をあるていど大きくしたほうが演算時間が短くなります"
    なのですね。勉強になりました。
    ありがとうございました。

    キャンセル

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

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

関連した質問

同じタグがついた質問を見る