埃氏筛法筛素数

发表于 | 更新于: | 分类于 | 阅读次数: |
字数统计: 835 字 | 阅读时长 ≈ 3 分钟

昨天实验课上，当我判断质数还在用取模方法的时候，打ACM的大佬刁老板对我说出埃氏筛，随后回到宿舍开始查，到现在整理完思路已经凌晨1点，在瑟瑟发抖中写下这篇博客。

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
下面用python实现

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
def JudgePrimes(n):
    primes = []
    f = []
    for i in range(n+1):#这样写，可以把自然数和列表元素的序号对应起来。
        if i > 2 and i%2 == 0:#把从0到n的偶数筛掉。
            f.append(0)
        else:
            f.append(1)
    i = 3
    while i*i <= n: #把不大于根号n的所有质数的倍数剔除,剩下的就是质数
        if f[i] == 1:#判断是不是质数，若是质数，则筛掉其倍数
            j = 2*i
            while j<=n:#把小于n的所有质数的倍数都筛掉
                f[j] = 0
                j += i 
            
        i += 2
 
    primes.append(2)#2是质数
    for x in range(3,n+1):
        if f[x] == 1:
            primes.append(x)
 
    return primes
 
n = int(input("请输入大于1的正整数n："))
primes = JudgePrimes(n)
print (primes)

算法可以进一步优化

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
def JudgePrimes(n):
    primes = []
    f = []
    for i in range(n+1):
        if i > 2 and i%2 == 0:
            f.append(0)
        else:
            f.append(1)
    i = 3
    while i*i <= n: #把不大于根号n的所有质数的倍数剔除,剩下的就是质数
        if f[i] == 1:#判断是不是质数，若是质数，则筛掉其倍数
            j = i*i #直接从质数的平方后开始筛，因为质数的平方之前的数已经被上一个质数筛过了，此时j为奇数
            while j <= n:
                f[j] = 0
                j += 2*i #如果只加一个i,j则为i的偶数倍是一个偶数已经被筛过了，所以加2个i筛掉i的奇数倍，小优化。
        i += 2
 
    primes.append(2)#2是质数
    for x in range(3,n+1,2):#步长为2，把偶数跳过,小优化。
        if f[x] == 1:
            primes.append(x)
 
    return primes
 
n = int(input("请输入大于1的正整数n："))
primes = JudgePrimes(n)
print (primes)

我的c语言抠脚，下面放上照着python写的c程序

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
#include <stdio.h>

int main()
{
	int n,j;
	scanf("%d",&n);
	int f[n+1];
	for(int i=0;i<=n;i++)
	{
		if(i>2&&i%2==0)f[i]=0;
		else f[i]=1;
	}
	int i =3;
	while(i*i<=n)
	{
		if(f[i] ==1)
		{
			j=i*i;
			while (j<=n)
			{
				f[j]=0;
				j+=2*i;
				
			}
		}
		i+=2;
	}
	f[2]=1;
	printf("2 ");
	for(int k=3;k<=n;k+=2)
	{
		if(f[k]==1)printf("%d ",k);
	}
	return 0;
}

然后我学到教材指针这部分，看见教材给了动态一维数组筛选法的例子。

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
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int i,j,n;
	int *s;
	do
	{
		printf("Please input n:\n");
		scanf("%d",&n);	
	} while (n<=0);
	s=(int*) calloc(n+1,sizeof(int));
	if(s==NULL)
	{
		printf("allocation failure");
		exit(1);
	}
	s[0]=s[1]=1;
	for(i=2;i<=n;i++)
	{
		if(s[i]==0)
		{
			for(j=2*i;j<n+1;j+=i)s[j]=1;
		}
	}
	for(i=0;i<=n;i++)
	{
		if(!s[i])printf("%5d",i);
	}
	free(s);
	return 0;
}