204. Count Primes 求素数
Description:
Count the number of prime numbers less than a non-negative number, n.
题目大意：
输出小于n的所有素数的个数。
思路：
采用厄拉多筛选法。
厄拉多塞筛法
西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。
其实，当你要画圈的素数的平方大于 n 时，那么后面没有划去的数都是素数，就不用继续判了。
代码实现如下：
|
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
|
class
Solution {
public
:
int
countPrimes(
int
n)
{
bool
*Del =
new
bool
[n];
//申请数组用来记录某个数字是否被标记
if
(n > 2)
Del[2] =
false
;
//先将数字2标记为素数
//某一数字标记为false表示该数为素数。
//某一数字标记为true表示该数为非素数。
for
(
int
i = 3;i<n;i++)
//将2的倍数都标记为非素数，将非2的倍数，标记为候选的素数。
{
if
(i % 2 == 0)
{
Del[i] =
true
;
}
else
Del[i] =
false
;
}
for
(
int
i = 3; i < n ;i++)
{
if
(!Del[i])
{
//如果当前数的平方大于目标数，那么当前数到
//目标数中间的所有数都是素数。
if
(i*i >=n)
break
;
for
(
int
j = 2;i*j < n; j++)
Del[i*j] =
true
;
}
}
int
count = 0;
for
(
int
i = 2;i < n;i++)
{
if
(!Del[i])
count++;
}
delete
[] Del;
return
count;
}
};
|
思路2：
耗时太长。
代码如下：
|
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
|
bool
isPrimes(
int
n)
{
if
(n == 2)
return
true
;
int
middle = (
int
)
sqrt
(
double
(n));
for
(
int
i = 2; i <= middle; i++)
{
if
(n % i == 0)
return
false
;
}
return
true
;
}
void
insertUnPrimesToSet(set<
int
> &myset,
int
n,
int
max,
int
flag)
{
int
times = (max-1) / n;
if
(flag == 0)
{
for
(
int
i = 1; i <= times; i++)
{
myset.insert(n*i);
}
}
else
if
(flag == 1)
{
for
(
int
i = 2; i <= times; i++)
{
myset.insert(n*i);
}
}
}
int
countPrimes(
int
n)
{
if
(n <= 2)
return
0;
set<
int
> myset;
//存放非素数
myset.insert(1);
for
(
int
i = 2; i < n; i++)
{
if
(myset.find(i) != myset.end())
continue
;
if
(!isPrimes(i))
//如果不是一个素数
{
insertUnPrimesToSet(myset, i, n,0);
}
else
//如果是一个素数
{
insertUnPrimesToSet(myset, i, n, 1);
}
}
return
n -1 - myset.size() ;
}
|
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837593
