如何更高效地检查数字是否为质数？

Question

我面临如下问题。他们给了我一个包含n个数字的数组，我需要使用“分治法”打印出其中是否包含任何质数。我已经解决了这个问题，但因为效率不高（据他们说），只得到了70/100的成绩。

#include <iostream>
using namespace std;

bool isPrime(int x){
   if(x == 2) return false;
   for(int i = 2; i <= x/2; ++i)
      if(x%i==0) return false;
   return true;

}

int existaP(int a[], int li, int ls){
    if(li==ls)
       if(isPrime(a[li]) == true) return 1;
       else return 0;
    else  return existaP(a, li, (li+ls)/2)+existaP(a, (li+ls)/2+1, ls);      
}

int main(){
   int n, a[10001];
   cin >> n;
   for(int i = 1; i<=n; ++i) cin >> a[i];
   if(existaP(a,1,n) >= 1) cout << "Y";
   else cout << "N";
   return 0;
}

- Andrei Radu

---

如果(x == 2)返回false; 这为什么会返回false？2是一个质数。 - Rivasa

existaP() 中递归的附加值是什么？输入数组是否已排序？ - rustyx

阅读素性测试维基页面。你的问题不是C++特定的，而且是离题的（因为在寻求资源...）。 - Basile Starynkevitch

Answer 1

这里最容易解决的问题是你的停止条件。

i <= x/2

可以替换为

i * i <= x

请确保您不会溢出int，因为您只需要到平方根x，而不是一半。也许i <= x / i 更好，因为它避免了溢出，尽管在某些平台上除法相对较耗时。

对于x == 2，您的算法也有缺陷，因为您返回的值是错误的。如果您省略那个额外的测试，后续的循环就涵盖了它，这将更好。

- Bathsheba

---

不需要到一半的位置，只需计算 x 的平方根即可。 - Bathsheba

Answer 2

bool isprime(int x)
{
    if(x <= 1) return false;
    if(x == 2 || x == 3) return true;
    if(x % 2 == 0 || x % 3 == 0) return false;
    if((x - 1) % 6 != 0 && (x + 1) % 6 != 0) return false;
    for(int i = 5; i * i <= x; i += 6)
    {
        if(x % i == 0 || x % (i + 2) == 0) return false;
    }
    return true;
}

如果需要打印特定范围内的素数或确定一个数是否为素数，建议使用厄拉多塞筛法算法，因为它在时间复杂度上非常高效，为O(n*log2(log2(n)))，但该算法的空间复杂度可能会在超过一定内存限制的情况下导致问题。

我们可以通过引入一些基于该定理的附加检查方法优化这个简单算法，其时间复杂度为O(n^1/2)，具体方法请参见上面的isprime代码块。

尽管厄拉多塞筛法算法在空间限制下的时间复杂度很高效，但是还可以利用上述提供的代码块，并且有许多变种的厄拉多塞筛法算法的性能表现更好，如此链接所述。

许多其他算法也存在，但在解决编程挑战方面，此算法更为简单和方便。您可以通过点击以下链接了解更多信息：
1. https://www.quora.com/Whats-the-best-algorithm-to-check-if-a-number-is-prime
2. https://www.baeldung.com/cs/prime-number-algorithms#:%7E:text=Most%20algorithms%20for%20finding%20prime,test%20or%20Miller%2DRabin%20method。

- K_Bhanu_Prakash

---

你能解释一下你的代码是如何更高效的吗？ - Miigon

Answer 3

这里有一个检查质数的高效方法。

 bool isPrime(int num) {
        if(num <= 1) return false;
        if (num <= 3)  return true; 
        
        int range = sqrt(num);
        // This is checked so that we can skip 
        // middle five numbers in below loop 
        if (num % 2 == 0 || num % 3 == 0) 
            return false; 
        

        for (int i = 5; i <= range; i += 6) 
            if (num % i == 0 || num % (i + 2) == 0) 
                return false; 
        
        return true;
    }

- Apurba Roy

---

太棒了！与我之前使用的素性测试相比，在1千万亿空间中，对于1,000个范围，节省了5秒的时间。 - Dshiz

Answer 4

一种标准的方法（也许是……？）就是从 i=0 遍历到 sqrt(number) 进行检查。

bool isPrime(int num){
    if(num == 1) return false;
    for(int i = 2;i<=sqrt(num);i++){
          if(num % i == 0) return false;
    }
    return true;
}

- user13500072

Answer 5

如果n为1，则您的代码将给出错误的答案。

您的时间复杂度可以降低到sqrt(n)，其中n是数字。

下面是代码：

bool isPrime(long int n)
{
  if (n == 1)
  {
    return false;
  }
  int i = 2;
  while (i*i <= n)
  {
      if (n % i == 0)
      {
          return false;
      }
      i += 1;
  }
  return true;
}

使用“long int”可以避免溢出问题。

希望这能有所帮助。:-)

- Arnab Sinha

Answer 6

如果数字不太大，您也可以尝试使用埃拉托斯特尼筛法来解决这个问题：

#include <iostream>
#include <array>

using namespace std;
constexpr int LIMIT = 100001;
// not_prime because global variables are initialized with 0
bool not_prime[LIMIT];

void sieve() {
    int i, j;
    not_prime[2] = false;

    for(int i = 2; i < LIMIT; ++i) 
        if(!not_prime[i])
            for(int j = i + i; j < LIMIT; j += i) 
                not_prime[j] = true;
}

int existaP(int a[], int li, int ls){
    if(li==ls)
       if(!not_prime[a[li]] == true) 
           return 1;
       else  
           return 0;
    else   
           return existaP(a, li, (li + ls) / 2) + existaP(a, (li + ls) / 2 + 1, ls);      
}

int main(){
   int n, a[10001];
   cin >> n;
   for(int i = 1; i<=n; ++i) cin >> a[i];

   sieve();

   if(existaP(a,1,n) >= 1) cout << "Y";
   else cout << "N";
   return 0;
}

基本上，当你遇到一个质数时，它的所有倍数都不是质数。

附言：我看到你是罗马尼亚人 :) 你可以在这里查看如何进一步优化算法：https://infoarena.ro/ciurul-lui-eratostene

- Alexandru Ica

Answer 7

在我看来，这是一个更快的算法。它基于欧几里得算法来计算H.C.F. 基本上，我检查数字和连续第二个数字的HCF是否为1；以及数字本身是否可被2或3整除。不要问我如何数学地得出解决方案，它只是突然想到了:D。这个解决方案的时间复杂度是O(log(max(a,b)))，明显比运行循环计数器2到sqrt(n)的程序的时间复杂度O(sqrt(n))小。

  #include <iostream>
    using namespace std;
    
    int hcf(int, int);
    
    int hcf(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
    
        return hcf(b, a % b);
    }
    
    int main()
    {
        int a;
    
        cout << "\nEnter a natural number: ";
        cin >> a;
    
        if(a<=0)
        {
            cout << "\nFor conventional reasons we keep the discussion of primes to natural numbers in this program:) (Read: Ring of Integers / Euclid's Lemma)";
            return 0;
        }
    
        if (a == 1)
        {
            cout << "\nThe number is neither composite nor prime :D";
            return 0;
        }
    
        if (a == 2)
        {
            cout << "\nThe number is the only even Prime :D";
            return 0;
        }
    
        if (hcf(a, a + 2) == 1)
        {
            if (a % 2 != 0 && a % 3 != 0)
            {
                cout << "\nThe number is a Prime :D";
                return 0;
            }
        }
    
        cout << "\nThe number is not a Prime D:";
    
        return 0;
    }

如果我错了，请指出来。我是一名学生。

- Paras Roy

---

我的 JavaScript 实现导致“最大调用堆栈大小超过了返回 a”的错误。 - Dshiz

当我输入25时，它说它是一个质数:D 哈哈 - IsaacMak

Answer 8

另一个尚未提到的低效率是 existaP(a, li, (li+ls)/2) + existaP(a, (li+ls)/2+1, ls);

特别地，这里的问题在于 +。如果你知道 existaP(a, li, (li+ls)/2) > 0，那么 existaP(a, (li+ls)/2+1, ls) 就不再重要了。换句话说，你目前正在计算唯一因子的确切数量，但是一旦你知道一个数字至少有两个因子，你就知道它不是质数。

- MSalters

Answer 9

这里有一种高效的方法来检查一个给定的数字是否为质数。

 bool isprime(int n) {
    if(n<=1)
        return false;

    if(n<=3)
        return true;

    if(n%2==0||n%3==0)
        return false;

    for(int i=5;i*i<=n;i=i+6) {
        if(n%i==0||n%(i+2)==0)
            return false;
    }

    return true;
}

- Saurabh Raj