Subscribed unsubscribe Subscribe Subscribe

1から、ある数より少ない数の中に含まれる素数を数えるには?

こんな感じかな

 

#include<stdio.h>
#include<math.h>

int prime(){
    
    int N;     // 与えられた数
    int flag; //素数か否かを判定するためのフラグ
    int ans = 0;

    for (int i = 3; i < N; i+=2) { //2の倍数を除く
        for (int j = 3; j <= sqrt(i); j+=2) { //約数を求める場合、ルートで得られた数以下のもので割り切れればOKなので
            flag = 0;
            if(i%j==0) {
                flag = 1;
                break; //割切れた時点で計算をカットして、計算量を減らす
            }
        }
        if (flag == 0) ans++;
    }
    printf("%d\n", ans);
}

 

参考資料

素数を求めるプログラム

次の問題の解き方を教えて下さい自然数nが,√n(ルートnです... - Yahoo!知恵袋