c++ - 当用户输入大量数字时无限循环

Question

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

• largestTwinPrime(0, 15485661) 会给我这个错误“程序超出了它的时间限制并被停止(可能是无限循环)”。
• largestTwinPrime(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;
    }
}

(最大双胞胎素数)

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(n²) 次，总计超过 O(n^2.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) 倍。

编辑

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