leetCode 204. Count Primes 哈希 求素数

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

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>countPrimes(</code><code>int</code> <code>n)</code>

<code>    </code><code>{</code>

<code>        </code><code>bool</code> <code>*Del = </code><code>new</code> <code>bool</code><code>[n];</code>

<code>        </code><code>//申请数组用来记录某个数字是否被标记</code>

<code>        </code><code>if</code><code>(n &gt; 2)</code>

<code>            </code><code>Del[2] = </code><code>false</code><code>;      </code>

<code>        </code><code>//先将数字2标记为素数</code>

<code>        </code><code>//某一数字标记为false表示该数为素数。</code>

<code>        </code><code>//某一数字标记为true表示该数为非素数。</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 3;i&lt;n;i++)   </code>

<code>        </code><code>//将2的倍数都标记为非素数，将非2的倍数，标记为候选的素数。</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(i % 2 == 0)</code>

<code>            </code><code>{</code>

<code>                </code><code>Del[i] = </code><code>true</code><code>;</code>

<code>            </code><code>}</code>

<code>            </code><code>else</code>

<code>                </code><code>Del[i] = </code><code>false</code><code>;</code>

<code>        </code><code>}</code>

<code>    </code> 

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 3; i &lt; n ;i++)</code>

<code>            </code><code>if</code><code>(!Del[i])</code>

<code>            </code><code>{</code><code>//如果当前数的平方大于目标数，那么当前数到</code>

<code>                </code><code>//目标数中间的所有数都是素数。</code>

<code>                </code><code>if</code><code>(i*i &gt;=n)</code>

<code>                    </code><code>break</code><code>;</code>

<code>                </code><code>for</code><code>(</code><code>int</code> <code>j = 2;i*j &lt; n; j++)</code>

<code>                    </code><code>Del[i*j] = </code><code>true</code><code>;</code>

<code>        </code><code>int</code> <code>count = 0;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 2;i &lt; n;i++)</code>

<code>                </code><code>count++;</code>

<code>        </code><code>delete</code> <code>[] Del;</code>

<code>        </code><code>return</code> <code>count;</code>

<code>    </code><code>}</code>

<code>};</code>

思路2：

耗时太长。

代码如下：

45

46

47

48

49

50

51

52

53

54

<code>bool</code> <code>isPrimes(</code><code>int</code> <code>n)</code>

<code>{</code>

<code>    </code><code>if</code> <code>(n == 2)</code>

<code>        </code><code>return</code> <code>true</code><code>;</code>

<code>    </code><code>int</code> <code>middle = (</code><code>int</code><code>)</code><code>sqrt</code><code>(</code><code>double</code><code>(n));</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = 2; i &lt;= middle; i++)</code>

<code>        </code><code>if</code> <code>(n % i == 0)</code>

<code>            </code><code>return</code> <code>false</code><code>;</code>

<code>    </code><code>return</code> <code>true</code><code>;</code>

<code>}</code>

<code>void</code> <code>insertUnPrimesToSet(set&lt;</code><code>int</code><code>&gt; &amp;myset, </code><code>int</code> <code>n,</code><code>int</code> <code>max,</code><code>int</code> <code>flag)</code>

<code>    </code><code>int</code> <code>times = (max-1) / n;</code>

<code>    </code><code>if</code> <code>(flag == 0)</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 1; i &lt;= times; i++)</code>

<code>            </code><code>myset.insert(n*i);</code>

<code>    </code><code>else</code> <code>if</code> <code>(flag == 1)</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 2; i &lt;= times; i++)</code>

<code>int</code> <code>countPrimes(</code><code>int</code> <code>n) </code>

<code>    </code><code>if</code> <code>(n &lt;= 2)</code>

<code>        </code><code>return</code> <code>0;</code>

<code>    </code><code>set&lt;</code><code>int</code><code>&gt; myset;</code><code>//存放非素数</code>

<code>    </code><code>myset.insert(1);</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = 2; i &lt; n; i++)</code>

<code>        </code><code>if</code> <code>(myset.find(i) != myset.end())</code>

<code>            </code><code>continue</code><code>;</code>

<code>        </code><code>if</code> <code>(!isPrimes(i))</code><code>//如果不是一个素数</code>

<code>            </code><code>insertUnPrimesToSet(myset, i, n,0);</code>

<code>        </code><code>else</code><code>//如果是一个素数</code>

<code>            </code><code>insertUnPrimesToSet(myset, i, n, 1);</code>

<code>    </code><code>return</code> <code>n -1 - myset.size() ;</code>

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837593