筛法求素数

level1:最原始的求素数方法

话不多说直接上代码（就是教科书上的）

#include <stdio.h>
#include <math.h>
int IsPrime(int x);
int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        if(IsPrime(i))
            printf("%d\n",i);
    }
    return 0;
}
int IsPrime(int x)
{
    int k,i;
    k=(int)sqrt(x);
    if(x<=1)
        return 0;
    for(i=2;i<=k;i++)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

level2:一般线性筛法

基本思路：先把某个范围的数全当成是素数，然后先给定0,1,不是素数。然后显然2就是最小的素数了，就是从2开始判定的。2是素数，先保存起来，那么2的倍数都不是素数了，标志为0.依次类推

3.4.5……. （注意这里面2的倍数有个技巧是从 i2 $i^2$ 开始而不是 i*2）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

void Prime(int n);
int main()
{
    int n;
    scanf("%d", &n);
    Prime(n);
    return 0;
}
void Prime(int n)
{
    int prime[n+10], cnt = 0;
    bool  mark[n+10];
    memset(mark, 1, sizeof(mark));//标记为0代表不是素数,1代表是素数。
    memset(prime, 0, sizeof(prime));//素数存储的地方
    mark[0] = 0;
    mark[1] = 0;
    //核心代码-----------------------
    for(int i=2; i<=n; i++)
    {
        if(mark[i])
        {
            prime[cnt++] = i;
            for(int j=i*i; j<=n; j+=i)
            {
                mark[j] = 0;
            }
        }
    }
    //------------------------------
    for(int i=0; i<cnt; i++)
    {
        printf("%d\n", prime[i]);
    }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
 

level 3:快速线性筛法

仔细分析可以发现第二种方法会造成重复筛除合数，影响效率。比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。所以，也就有了快速线性筛法。

分析：
利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

void Prime(int n);
int main()
{
    int n;
    scanf("%d", &n);
    Prime(n);
    return 0;
}
void Prime(int n)
{
    int prime[n+10], cnt = 0;
    bool  mark[n+10];
    memset(mark, 1, sizeof(mark));//标记为0代表不是素数,1代表是素数。
    memset(prime, 0, sizeof(prime));//素数存储的地方
    mark[0] = 0;
    mark[1] = 0;//这两个肯定不是素数了
    for(int i=2; i<=n; i++)
    {
        if(mark[i])//是素数就存起来
        {
            prime[cnt++] = i;
        }
        for(int j=0; j<cnt && i*prime[j]<=n; j++)
        {
            mark[i*prime[j]] = 0;

            if(i % prime[j] == 0)
                break;
        }
    }
    for(int i=0; i<cnt; i++)
    {
        printf("%d\n", prime[i]);
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

拓展阅读：
较易懂的解释
较准确的解释

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/54880747