如何以最簡捷的方法求出兩個數之間的素數個數?
這個數據範圍不是一遍歐拉篩預處理一下就完事了嘛
for (int i = 2; i &<= n; i++) // 歐拉篩 O(n)
{
if (!vis[i]) prime[cnt++] = i;
for (int j = 0; j &< cnt; j++)
{
if (i * prime[j] &> n) break;
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
瀉藥
歐拉篩飛過去
當然閹割的洲閣篩它不香麼？
篩素數就可以了。埃氏篩已經夠快了，加上質因數可以加速
求l～r素數個數就是2～r個數-2～l-1，這樣速度很快也很好寫
最簡單但時間不保證就是寫個循環判斷
還有作業自己做
推薦閱讀：
