[Lv.1]少数を探す

📝 質問する

小数点を検索

💡 の意見を打診

最初はシンプルなダブルforゲート
最初のforゲート-i:2~n
2番目のforゲート-j:2~i
回転してタイムアウトしました.
平方根の前に範囲を設定し、偶数を除外し、末数の5桁を除外するなど...試したが、効率テストでは1、2つの改訂度が合格しなかった.
最終的に通過する方法.
1)小数点以下のベクトルを作成
2)n>=3の場合、ベクトルに3を加算(偶数は除外されるので2を加算しない)
3)for文を迂回して小数ベクトル内の要素に分割するかどうかをチェックする
4)切り離し
5)ベクトルの要素が平方根より大きい場合は小数であるため、小数ベクトルに入れて中断する

💻 コード#コード#

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    vector<int> v;	// 소수를 넣을 벡터
    if(n>=3) v.push_back(3);
    
    for(int i=5; i<=n; i=i+2){	// 3보다 크며 가장 작은 소수인 5부터, i에 2씩 더해주며 짝수 배제
        for(int j=0; j<v.size(); j++){
            if(i%v[j]==0) break;	// 소수로 나누어 떨어지면 소수가 아님
            if(v[j]>sqrt(i)){	// 제곱근보다 작거나 같은 수로 나누어 떨어지지 않는다면 소수이다
                v.push_back(i);
                break;
            }  
        }
    }
    
    return v.size()+1;	// 소수 벡터에 넣지 않은 2를 더해줌
}

とにかく上のコードでテストに合格しました...より効果的なソリューションが得られました.
エラトネスのふるいを利用して少数の排水を消す方法!

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> tmp(n+1, true);

    for (int i=2; i<n+1; i++) {
        if (tmp[i] == true) {
            answer++;
            for (int j=2; i*j<=n; j++) 
                tmp[i*j] = false;	// 소수 i의 배수들을 모두 false로 바꿔줌
        }
    }

    return answer;
}

すべての数字を迂回したい場合は、少数に分けられない(for an if)を選択します.
上のコードは小数点に分けるものを事前に排除しています.ドアの周りを回っているので、効率が高いです.(ifのfor)
今日も考える力を養い、


私の解答とより効率的な解答の実行結果!速度差が大きいのが見えます.