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);
}
参考資料