判断素数个数

Z·Ton·Y · 2019-08-03 21:34:30 · 题解

判断素数个数

Prime

• 【题意简述】

  求X与Y之间的素数个数。

• 【算法】

  线性筛

• 【代码】 （O(n))

#include<bits/stdc++.h>
using namespace std;
int X,Y,cnt,ans,p[100001];
bool prime[100001];
int main() {
    cin>>X>>Y;
    if (X>Y)
        swap(X,Y);
    prime[1]=1;
    for(int i=2;i<=Y;i++)
    {
        if(!prime[i]) 
            p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=Y;j++)
        {
            prime[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
    for (int i=X;i<=Y;i++)
        if (!prime[i])
            ans++;
    cout<<ans<<endl;
    return 0;
}

题目来源 (节选自20190801模拟赛）