欧拉线筛

素数个数

code:

#include<bits/stdc++.h>
using namespace std;
int n;  
bool vis[100000000];//判断是否为素数 
int Isprime[5800000];//记录存储素数
int cnt=0;//cnt代表素数的个数
void prime(int x)
{  
    if(x==1)return ;
    for(int i=2;i<=x;i++){
        if(!vis[i]){//vis表示0为素数，1为合数
            Isprime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*Isprime[j]<=x;j++){
            vis[Isprime[j]*i]=true;
            //此时  Isprime[j]为依次最小素数，Isprime[j] 一定是 i 的最小素数
            if(i%Isprime[j]==0)break;
            //欧拉筛法的核心语句：判断去重
            //因为 Isprime[j]的倍数一定被标记过且为合数，
            //所以当 i 为其倍数时直接break掉 ; 减少重复运算
            
        }
    }
    return ;
}
int main(){
    scanf("%d",&n);
    prime(n);
    printf("%d
",cnt);
}

完美AC,注意数据范围，防止RE

判断素数：

题目：传送门

code：

 1 #include<bits/stdc++.h>
 2 using namespace std;    
 3 int a,b,ans=0;
 4 /*int dif(int n)
 5 {
 6     int temp=0,nn=0;
 7     while(n!=0)
 8     {
 9         temp=temp*10+n%10;
10         n=n/10;
11     }
12     return temp;
13 }*/
14 bool prim(int s)
15 {
16     if(s<=1)
17     return false;
18     for(int i=2;i*i<=s;i++)
19         if(s%i==0)return false;
20         //else return true;
21     return true;
22 }
23 int main()
24 {
25 
26     cin>>a;
27     if(prim(a))
28     cout<<"YES"<<endl;
29     else
30     cout<<"NO"<<endl;
31 }