c++ - 使递归在 C++ 中更高效

Question

我用C++写了下面的递归

#include <iostream>
#include <stdlib.h>
#include <math.h>

#define N 100
using namespace std;


long long int recursion(int array[], int begin,int end, long long int now){
    if(now>N){
        return 0;
    }
    else{
        long long int huge_number=N/now;
        for(int i=1;i<end-begin;i++){
            huge_number=huge_number-recursion(array,begin+i,end,now*array[begin+i]);
        }
        return huge_number;
    }
}

int main(int argc, const char * argv[]) {
    int array[4]={2,3,5,7};
    /*FILE * pFile;
    pFile = fopen ("primes.txt","r");
    for(int i=0;i<78498;i++){
        fscanf(pFile, "%d", &priemen[i]);
    }
    fclose(pFile);*/ 
    //I have actually a txt file with primes less than 10^6
    int number_divisible[4];//this array will contain the desired numbers as explained below
    for(int i=0;i<4;i++){
        number_divisible[i]=N/array[i];
        for(int j=0; j<i;j++){
            number_divisible[i]=number_divisible[i]-recursion(array,j,i,array[i]*array[j]);
        }
    }
    return 0;
}

此代码执行以下操作:以 N=100 为例。该数组将由不超过 N 的平方根的素数组成，因此数组 = {2,3,5,7}。通过这种递归，我们可以计算出 2 到 100 之间有多少数是 {2,3,5,7} 中素数 p 的倍数，但不是小于 p 的素数的倍数。

如果我想将它用于巨大的数字 N，比如 10^9，那么程序将花费太多时间来完成。

我的问题是我们是否可以优化上面给出的代码。如果不能，那么我必须找到一种不同的算法来计算上面解释的所需数字。

Answer 1

提高递归性能的一种方法是将参数数量减少到所需的最低限度。

另一种方法是用迭代代替递归。这需要算法分析或洞察力。

还有一种方法是减少递归级别。这也需要分析和洞察。

浏览一下您的代码后，通过添加一个数组来跟踪先前计算的值，迭代替换似乎已经成熟。