针对第 n 个素数执行时间优化的 c++ 函数

Question

我正在实现一个 c++ 函数，以使用一些预定义的索引来获得第 N 个素数，以达到时间优化的目的。

我的代码是：

// file prime.cpp

#include <iostream>
#include <time.h>
using namespace std;

/*
#define primeAt10000 104743
#define primeAt20000 224743
#define primeAt30000 350381
#define primeAt40000 479951
#define primeAt50000 611977
*/

int prime(int n){
    int pos = 1,i = 1,temp;
    if(n==0)
        return 2;
    /*
    else if(n>50000){
        i = primeAt50000;
        pos = 50001;
    }else if(n>40000){
        i = primeAt40000;
        pos = 40001;
    }else if(n>30000){
        i = primeAt30000;
        pos = 30001;
    }else if(n>20000){
        i = primeAt20000;
        pos = 20001;
    }else if(n>10000){
        i = primeAt10000;
        pos = 10001;
    }*/

    while( i+=2 ){
        temp = i/2+1;
        for(int j = 3 ; j <= temp ; j+=2)
            if(i%j == 0)
                goto con;
        if(pos++ >= n)
            return i;
        con :;
    }
}

int main(int argc, char const *argv[]){
    int index;
    cin >> index;
    clock_t start = clock();
    cout << prime(index)<<endl;
    cout << (clock()-start)/CLOCKS_PER_SEC<<"sec"<< endl; 
    return 0;
}

编译为：

g++ prime.cpp -o prime.exe

我运行输入9999、19999和29999输入3次此代码

第 1 运行：1 秒 6 秒 14 秒

第 2 运行：1 秒 7 秒 15 秒

第 3 运行：1 秒 7 秒 16 秒

再次启用注释代码后，我使用相同的输入运行三次

第 1 运行：1 秒 5 秒 8 秒

第 2 运行：1 秒 5 秒 8 秒

第 3 运行：1 秒 5 秒 8 秒

我的问题是：

为什么第二次编译后每次执行所用的时间有差异，而循环每次运行ning 约 1,25,000 次？

和

为什么输入 19999（~104743 次循环）比第一次编译后的前 3 运行s（~224743 次循环）更接近？

Answer 1

在与@JonathanLeffler 讨论后，我进一步优化了此函数，以便为较大的输入值（如索引 9999、19689 等）实现最快的输出...

现在我的质数函数的复杂度是 (N^2)/12，与之前不同 [它是 (N^2)/8]。

我的新密码是：

#include <iostream>
#include <time.h>

using namespace std;

#define primeAt10000 104743-7
#define primeAt20000 224743-7
#define primeAt30000 350381-7
#define primeAt40000 479951-7
#define primeAt50000 611977-7

bool checkPrime(int x){
    int temp = x/2+1;
    for(int j = 3 ; j <= temp ; j+=2)
        if(x%j == 0)
            return false;
    return true;
}

int prime(int n){
    int pos = 2,i = 0;

    if(n==0)
        return 2;
    else if(n==1)
        return 3;
    else if(n>50000){
        i = primeAt50000;
        pos = 50000;
    }else if(n>40000){
        i = primeAt40000;
        pos = 40000;
    }else if(n>30000){
        i = primeAt30000;
        pos = 30000;
    }else if(n>20000){
        i = primeAt20000;
        pos = 20000;
    }else if(n>10000){
        i = primeAt10000;
        pos = 10000;
    }

    while( i+=6 ){
        if(checkPrime(i-1))
            if(pos++>=n)
                return i-1;
        if(checkPrime(i+1))
            if(pos++>=n)
                return i+1;
    }
    return 0;
}

int main()
{
    int index;
    cin >> index;
    clock_t start = clock();
    cout << prime(index)<<endl;
    cout << (clock()-start)/(float)CLOCKS_PER_SEC<<"sec";
    return 0;
}

编译（根据@NathanOliver && @JonathanLeffler 的建议）：

g++ -O3 -Wall -Werror -Wextra prime.cpp -o prime.exe

现在 prime.exe 输入 9999、19999 和 29999 分别需要 1.34、4.83 和 7.20 秒。

Answer 2

每个 9999 间隔的时间差异是不同的，因为当我们转向较大的数字来检查它是否为素数时，它比较小的数字需要更多的时间。

换句话说直接我们可以说prime()中for-loop的运行时间增加了，因为变量temp的值变大了。

当我们检查 i = 101 时，temp 的值变为 51，for 循环将运行大约 25 次。

而当我们检查 i = 10001 时，temp 的值变为 5001，for 循环将运行大约 2500 次。

for 循环运行时间的这种差异会增加您的整体时间复杂度。

针对第 n 个素数执行时间优化的 c++ 函数

Optimized c++ function for nth prime number execution time

c++

debugging

g++