春暖花开

埃拉托色尼筛选法

埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.~194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的,用于求一定范围内的质数。

步骤:

(1)先把1删除(现今数学界1既不是质数也不是合数);

(2)读取队列中当前最小的数2,然后把2的倍数删去;

(3)读取队列中当前最小的数3,然后把3的倍数删去;

(4)读取队列中当前最小的数5,然后把5的倍数删去;

(5)如上所述直到需求的范围内所有的数均删除或读取;

今天,无意中看到这一算法,觉得很好,便用 C 语言来实现了该算法。采用链表作为数据结构,并通过递归筛选。下面是实现的 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//埃拉托色尼筛选法
#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode{
int data;
struct LinkNode *next;
}LinkNode, *LinkList;
//创建一个链表存储的从1到n的数组
LinkList Create( int n){
LinkList L,p;
int i;
L = (LinkList) malloc (sizeof(LinkNode));
if(!L)
exit(0);
L->next = NULL;
for( i = n; i > 0; i-- ){
p = (LinkList) malloc (sizeof(LinkNode));
if ( !p ) {
exit(0);
}
p->data = i;
p->next = L->next;
L->next = p;
}
return L;
}
//求出所有素数(递归加筛选)
void Prime(LinkList L, int n){
static int i = 0;
int state;
LinkList p, q, r, s;
state = i;
p = L;
q = p->next;
while(state--){
p = p->next;
q = q->next;
}
if (q == NULL || 2*q->data > n) //终止
return;
else if(q->data == 1){ //删除1
r = p;
p->next = q->next;
free(r);
i++;
Prime(L, n);
return;
}
else{ //删除第一个的所有倍数
int value = p->data;
LinkList temp;
while(q){
if (q->data % value == 0){
p->next = q->next;
temp = q;
q = q->next;
free(temp);
}
if( !q )
break;
p = p->next;
q = q->next;
}
i++;
Prime(L, n);
return;
}
}
LinkList Create(int n);
void Prime(LinkList L, int n);
void PrintList(LinkList L);
//打印值
void PrintList(LinkList L){
int i = 1;
while( L->next ){
printf( "%d\t", L->next->data );
if(i%7 == 0)
printf( "\n" );
i++;
L = L->next;
}
printf( "\n" );
}
int main( int argc, char **argv ) {
LinkList p;
int n;
printf( "Enter number:" );
scanf("%d", &n);
p = Create(n);
PrintList(p);
Prime(p, n);
printf( "Prime:\n" );
PrintList(p);
return 0;
}
0%