用户输入大数字时的无限循环

Question

我正在写一个名为largestTwinPrime的函数，它接收2个数字并找到两者之间最大的孪生素数。我的程序工作但是当用户输入足够大的数字时，程序变成无限循环。例如：

• maximumTwinPrime（0,15485661）会给我这个错误“程序超过了它的时间限制并且被停止（可能是无限循环）”。
• maximumTwinPrime（1,18）将输出17。

这是我的代码，感谢您的帮助！

（伊斯普拉到）

int isPrime(int num){
    if(num <= 1) return 0;
    for (int i = 2; i * i <= num; i++){
        if (num % i == 0) return 0;
    }
    return 1;
}

（isTwinPrime）

bool isTwinPrime(int n){
    if(n <= 1) return 0;
    if(isPrime(n+2)==true && isPrime(n)==true){
        return 1;
    } else if(isPrime(n-2)==true && isPrime(n)==true){
        return 1;
    } else{
        return 0;
    }
}

（largestTwinPrime）

int largestTwinPrime(int a, int b){
    int answer=0;
    while(a <= b){
        for(int i = a; i <= b; i++){
            if(isTwinPrime(i)== true){
                answer = i;
            }
        }
        a++;
    }
    if(answer==0) return -1;
    else return answer;
}

Answer 1

您的代码的复杂性非常低。您的代码调用isTwinPrime O（n2）次，总计超过O（n2.5）。这使它看起来像一个无限循环：

while(a <= b){ // O(N) iterations
    for(int i = a; i <= b; i++){
        // times O(N) = O(N**2)
        if(isTwinPrime(i)== true){ // The call is over O(sqrt(N))
            answer = i;
        }
    }
    a++;
}

正确的代码是：

int largestTwinPrime(int a, int b){
    int answer=0;
    if (b < 5) return -1;
    // A twin prime is odd, so go over odd values.
    if (b %2 == 0) b--; 
    for(int i = b; i >= a; i-=2){
            if(isTwinPrime(i))
                return i;
    }
    return -1;
}

复杂度降低了O（N）倍。

EDIT

此外，您的isPrime效率低下。最好填充低于sqrt（N）的素数向量（使用Sieve of Eratosthenes），并使用它来加速质数的验证。