** 两种筛素数的方法：** <Excerpt in index | 首页摘要>
<The rest of contents | 余下全文>
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
104
105
106
107
| 筛选法求素数：
void getprime()
{
int i,j;
memset(b,1,sizeof(b));
b[0]=0;
b[1]=0;
for(i=2;i*i<=100000;i++)
{
if(b[i])
{
for(j=i*i;i<=100000;j+=i)
{
p[j]=0;
}
}
}
}
快速判断一个数是否为素数
bool isPrime(int num)
{
if (num == 2 || num == 3)
{
return true;
}
if (num % 6 != 1 && num % 6 != 5)
{
return false;
}
for (int i = 5; i*i <= num; i += 6)
{
if (num % i == 0 || num % (i+2) == 0)
{
return false;
}
}
return true;
}
快速求一个数以内的所有素数
#define N 100000000
bool notPrime[N+5];
void ScreeningPrime(void)
{
int i, j, increment[6] = {0, 4, 0, 0, 0, 2};
for (i = 5; i*i <= N; i += increment[i%6])
{
for (j = i; i*j <= N; j += increment[j%6])
{
notPrime[i*j] = true;
}
}
}
|
