PAT乙级1007

1007 素数对猜想（20 分)

让我们定义

现给定任意正整数N(

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

输出样例:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int check[100005];
 4 int prime[100005];
 5 int tot,ans;
 6 int main()
 7 {
 8     for(int i=2;i<100002;i++)
 9     {
10         if(!check[i])
11             prime[tot++]=i;
12         for(int j=0;j<tot;j++)
13         {
14             if(prime[j]*i>100000)
15                 break;
16             check[i*prime[j]]=1;
17             if(i%prime[j]==0)
18                 break;
19         }
20     }
21     int n;
22     cin>>n;
23     for(int i=1;prime[i]<=n;i++)
24     {
25         if(prime[i]-prime[i-1]==2)ans++;
26     }
27     cout<<ans;
28     return 0;
29 }

利用欧式筛找素数

欧拉筛

算法思路

对于一个数x，筛掉小于x最小质因子的质数乘以x的数

举个栗子：66=2*3*11 ，66的最小质因子为2 不筛

77=7*11，77的最小质因子为7 小于7的质数为2 3 5 ，筛去2*77，3*77，5*77

算法证明

1.没有重复筛

假设一个合数分解成P=p1*p2*p3，保证p1<=p2<=p3,那么筛去这个数的机会有：p1*(p2*p3),p2*(p1*p3),p3*(p1*p2).

我们把一个合数分解为A=a1*a2*a3(a1<=a2<=a3)，筛去合数P， P=(小于a1的质数)*A，

所以筛去P唯一的可能是p1*(p2*p3)，所以不会重复筛

2.没有漏筛

把这个合数分解质因数P=a*b*c,保证a<=b<=c然后设s=b*c,s<P,说明在s出现时，P已经被筛掉了。

for(int i=2;i<100005;i++){
        if(!check[i])
          prime[t++]=i;
        for(int j=0;j<t;j++)
        {
            if(prime[j]*i>100000)break;
            check[i*prime[j]]=1;
            if(!i%prime[j])
                break;
        }
    }