SolutionsForLeetcode/Count_Primes.cpp at master · lhuang9703/SolutionsForLeetcode · GitHub

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
// Source : https://leetcode-cn.com/problems/count-primes/description/
// Number : 204
// Author : HL
// Date   : 2018-09-09
// Kill   : 21.53%，86.60%

/**********************************************************************************
Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
**********************************************************************************/

class Solution {
public:
    int countPrimes(int n) {
        // 隔数判断法
        // if(n <= 2)
        //     return 0;
        // else if(n == 3)
        //     return 1;
        // else{
        //     int count = 0,k,t;
        //     for(k=3; k<n ; k+=2){
        //         count++;
        //         for(t=3; t<=sqrt(k); t+=2)
        //             if(k%t == 0){
        //                 count--;
        //                 break;
        //             }
        //     }
        //     return count+1;//把2这个质数加进去
        // }

        // 厄拉多塞筛法
        bool *arr = new bool[n];
        arr[1] = false;
        arr[2] = true;
        int i,j;
        for(i=3; i<n; i++){
            if(i%2 == 0)
                arr[i] =false;
            else
                arr[i] = true;
        }
        for(i=3; i<n; i+=2){
            if(arr[i]){
                for(j=2; i*j<n; j++)
                    arr[i*j] = false;
            }
        }
        int count = 0;
        for(i=1; i<n; i++)
            if(arr[i])
                count++;
        delete arr;
        return count;
    }
};