用C++判断素数和统计素数的时间效率

- 素数判断
- - 方法一
  - *方法二
  - 方法三
  - 运行结果
- 统计素数
- - 方法一（使用素数判断方法二来统计）
  - 方法二（使用素数判断方法三来统计）
  - *方法三（将不是素数的数排除，埃氏筛）
  - 方法四（在埃氏筛的基础上，减少重叠，线性筛）
  - 实验结果
- 总结
- 全部程序
- 参考&感谢

素数判断方法一

//素数判断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;
    }

运行结果

	//主程序
	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
    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 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 primes;
        vector 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();
    }

实验结果

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.素数判断需要掌握方法二，了解方法三；素数统计中需要掌握方法三，了解方法四。

全部程序

main.cpp主程序

#include 
#include 
#include 

#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;
}

solve2.h头文件

#ifndef CLIONTEST_SOLVE2_H
#define CLIONTEST_SOLVE2_H

#include 
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 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 primes;
        vector 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

参考&感谢

素数的判断
素数的统计
C++程序运行时间测试

用C++判断素数和统计素数的时间效率

C/C++/C#相关栏目本月热门文章