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

Question

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) //２以上で、同じ数字以外で割り切れた時は素数ではない
                    isSosu=false;
                
            }
           
            if(isSosu)
                count++;
        } 
        return count;
    }
};

Answer 1

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

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

Comments

[alizona]

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

[alizona]

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

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

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

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

Answer 2

例えば、「同じ数字以外で割り切れた時は素数ではない」の判断をする前に、「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が大きい時には使う素数の数をあるていど大きくしたほうが演算時間が短くなります。

Comments

[alizona]

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

Answer 3

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

Comments

[alizona]

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