用C++判断素数和统计素数的时间效率_c++ bool判断十万需要多久

作者：你好赵伟 | 2024-02-10 19:43:59

踩

c++ bool判断十万需要多久

素数判断

方法一

//素数判断1
    bool isPrime1(int num)
    {
        if (num <= 3) return num > 1;
        for (int i = 2; i < num; i++)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10

*方法二

//素数判断2
    bool isPrime2(int num)
    {
        if (num <= 3) return num > 1;
        int sq = (int)sqrt(num);
        for (int i = 2; i <= sq; i++)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11

方法三

//素数判断3
    bool isPrime3(int num)
    {
        if (num <= 3) return num > 1;
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sq = (int)sqrt(num);
        for (int i = 5; i <= sq; i += 6) {
            //6的倍数的前后两个数可能是质数，也有可能是质数的倍数，下面是将其排除
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果

	//主程序
	int main()
	{   int num = 2147483647; // 这是一个素数
	    PrimeNumber p;
	    long t1_1 = GetTickCount();					//开始时间
	    cout << "isPrime1: " << p.isPrime1(num) << endl;
	    long t1_2 = GetTickCount();                   //结束时间
	    cout << "1:素数判断消耗时间：" << t1_2 - t1_1 << "ms" << endl;
	    long t2_1 = GetTickCount();					//开始时间
	    cout << "isPrime2: " << p.isPrime2(num) << endl;
	    long t2_2 = GetTickCount();                   //结束时间
	    cout << "2:素数判断消耗时间：" << t2_2 - t2_1 << "ms" << endl;
	    long t3_1 = GetTickCount();					//开始时间
	    cout << "isPrime3: " << p.isPrime3(num) << endl;
	    long t3_2 = GetTickCount();                   //结束时间
	    cout << "3:素数判断消耗时间：" << t3_2 - t3_1 << "ms" << endl;
	    return 0;
	}
	//运行结果
	num = 2147483647
	isPrime1: 1
	1:素数判断消耗时间：5844ms
	isPrime2: 1
	2:素数判断消耗时间：0ms 
	isPrime3: 1
	3:素数判断消耗时间：0ms
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

统计素数

方法一（使用素数判断方法二来统计）

	//统计素数1
    int countPrime1(int num)
    {
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            res += isPrime2(i);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10

方法二（使用素数判断方法三来统计）

    //统计素数2
    int countPrime2(int num)
    {
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            res += isPrime3(i);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10

*方法三（将不是素数的数排除，埃氏筛）

	//统计素数3, 排除不是素数的数
    int countPrime3(int num)
    {
        vector<int> isP(num, 1);
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            if (isP[i])
            {
                res += 1;
                if ((long long) i * i < num)
                {
                    for (int j = i * i; j < num; j += i)
                    {//将i的倍数的数置为false,表示不是素数
                        isP[j] = 0;
                    }
                }
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法四（在埃氏筛的基础上，减少重叠，线性筛）

    //统计素数4, 线性筛选
    int countPrime4(int n) {
        vector<int> primes;
        vector<int> isPrime(n, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                //把素数存起来
                primes.push_back(i);
            }
            for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
                isPrime[i * primes[j]] = 0;
                if (i % primes[j] == 0) {
                    break;
                }
            }
        }
        return primes.size();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实验结果

int main()
{   int num = 10000000;
    PrimeNumber p;
    long t4_1 = GetTickCount();					//开始时间
    cout << "countPrime1: " << p.countPrime1(num) << endl;
    long t4_2 = GetTickCount();                   //结束时间
    cout << "1:统计素数消耗时间：" << t4_2 - t4_1 << "ms" << endl;
    long t5_1 = GetTickCount();					//开始时间
    cout << "countPrime2: " << p.countPrime2(num) << endl;
    long t5_2 = GetTickCount();                   //结束时间
    cout << "2:统计素数消耗时间：" << t5_2 - t5_1 << "ms" << endl;
    long t6_1 = GetTickCount();					//开始时间
    cout << "countPrime3: " << p.countPrime3(num) << endl;
    long t6_2 = GetTickCount();                   //结束时间
    cout << "3:统计素数消耗时间：" << t6_2 - t6_1 << "ms" << endl;
    long t7_1 = GetTickCount();					//开始时间
    cout << "countPrime4: " << p.countPrime4(num) << endl;
    long t7_2 = GetTickCount();                   //结束时间
    cout << "4:统计素数消耗时间：" << t7_2 - t7_1 << "ms" << endl;

    return 0;
}

//运行结果
num = 10000000
countPrime1: 664579
1:统计素数消耗时间：5985ms
countPrime2: 664579
2:统计素数消耗时间：1906ms
countPrime3: 664579
3:统计素数消耗时间：297ms
countPrime4: 664579
4:统计素数消耗时间：281ms
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

总结

1.在素数判断中，效率：方法三 > 方法二 > 方法一。
2.在素数统计中，效率：方法四 > 方法三 > 方法二 > 方法一。
3.素数判断需要掌握方法二，了解方法三；素数统计中需要掌握方法三，了解方法四。

全部程序

main.cpp主程序

#include <bits/stdc++.h>
#include <algorithm>
#include <windows.h>

#include "solve2.h"

using namespace std;

int main()
{   int num = 2147483647; // 这是一个素数
    PrimeNumber p;
    long t1_1 = GetTickCount();					//开始时间
    cout << "isPrime1: " << p.isPrime1(num) << endl;
    long t1_2 = GetTickCount();                   //结束时间
    cout << "1:素数判断消耗时间：" << t1_2 - t1_1 << "ms" << endl;
    long t2_1 = GetTickCount();					//开始时间
    cout << "isPrime2: " << p.isPrime2(num) << endl;
    long t2_2 = GetTickCount();                   //结束时间
    cout << "2:素数判断消耗时间：" << t2_2 - t2_1 << "ms" << endl;
    long t3_1 = GetTickCount();					//开始时间
    cout << "isPrime3: " << p.isPrime3(num) << endl;
    long t3_2 = GetTickCount();                   //结束时间
    cout << "3:素数判断消耗时间：" << t3_2 - t3_1 << "ms" << endl;

    cout << "..........................." << endl;
    num = 10000000;
    long t4_1 = GetTickCount();					//开始时间
    cout << "countPrime1: " << p.countPrime1(num) << endl;
    long t4_2 = GetTickCount();                   //结束时间
    cout << "1:统计素数消耗时间：" << t4_2 - t4_1 << "ms" << endl;
    long t5_1 = GetTickCount();					//开始时间
    cout << "countPrime2: " << p.countPrime2(num) << endl;
    long t5_2 = GetTickCount();                   //结束时间
    cout << "2:统计素数消耗时间：" << t5_2 - t5_1 << "ms" << endl;
    long t6_1 = GetTickCount();					//开始时间
    cout << "countPrime3: " << p.countPrime3(num) << endl;
    long t6_2 = GetTickCount();                   //结束时间
    cout << "3:统计素数消耗时间：" << t6_2 - t6_1 << "ms" << endl;
    long t7_1 = GetTickCount();					//开始时间
    cout << "countPrime4: " << p.countPrime4(num) << endl;
    long t7_2 = GetTickCount();                   //结束时间
    cout << "4:统计素数消耗时间：" << t7_2 - t7_1 << "ms" << endl;

    return 0;
}
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

solve2.h头文件

#ifndef CLIONTEST_SOLVE2_H
#define CLIONTEST_SOLVE2_H

#include <bits/stdc++.h>
using namespace std;

class PrimeNumber
{
public:
    //素数判断1
    bool isPrime1(int num)
    {
        if (num <= 3) return num > 1;
        for (int i = 2; i < num; i++)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
    //素数判断2
    bool isPrime2(int num)
    {
        if (num <= 3) return num > 1;
        int sq = (int)sqrt(num);
        for (int i = 2; i <= sq; i++)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
    //素数判断3
    bool isPrime3(int num)
    {
        if (num <= 3) return num > 1;
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sq = (int)sqrt(num);
        for (int i = 5; i <= sq; i += 6) {
            //6的倍数的前后两个数可能是质数，也有可能是质数的倍数，下面是将其排除
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    //统计素数1
    int countPrime1(int num)
    {
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            res += isPrime2(i);
        }
        return res;
    }

    //统计素数2
    int countPrime2(int num)
    {
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            res += isPrime3(i);
        }
        return res;
    }

    //统计素数3, 排除不是素数的数
    int countPrime3(int num)
    {
        vector<int> isP(num, 1);
        int res = 0;
        for (int i = 2; i < num; i++)
        {
            if (isP[i])
            {
                res += 1;
                if ((long long) i * i < num)
                {
                    for (int j = i * i; j < num; j += i)
                    {//将i的倍数的数置为false,表示不是素数
                        isP[j] = 0;
                    }
                }
            }
        }
        return res;
    }

    //统计素数4, 线性筛选
    int countPrime4(int n) {
        vector<int> primes;
        vector<int> isPrime(n, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                //把素数存起来
                primes.push_back(i);
            }
            for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
                isPrime[i * primes[j]] = 0;
                if (i % primes[j] == 0) {
                    break;
                }
            }
        }
        return primes.size();
    }
};



#endif //CLIONTEST_SOLVE2_H

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
108
109
110
111
112
113
114
115
116

参考&感谢

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/75317