如何以更有效的方式检查数字是否为素数？

Question

所以我有以下问题。他们给了我一个有 n 个数字的数组，如果它包含任何质数，我必须使用 "Divide et Impera" 打印出来。我解决了这个问题，但它只得到 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;
}

Answer 1

这里最容易挂的果子是你的停止条件

i <= x/2

可以替换为

i * i <= x

注意确保您不会溢出 int。这是因为您只需要达到 x 的平方根，而不是一半。也许 i <= x / i 更好，因为它避免了溢出；尽管以在某些平台上成本相对较高的部门为代价。

您的算法对于 x == 2 也是有缺陷的，因为您的 return 值不正确。如果你放弃那个额外的测试会更好，因为随后的循环会覆盖它。

Answer 2

如果 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" 将有助于避免溢出。

希望这对您有所帮助。 :-)

Answer 3

如果数字不是太大你也可以尝试用Eratosthenes筛法来解决这个问题：

#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;
}

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

P.S.: Acum am vazut ca esti roman :) Poti sa te uiti aici pentru a optimiza si mai mult algoritmul: https://infoarena.ro/ciurul-lui-eratostene

Answer 4

另一个尚未提及的低效率是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) 就不再重要了。换句话说，您目前正在计算确切个独特因素，但是一旦您知道一个数字有至少两个因素，您知道这不是素数。

Answer 5

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

 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;
}

Answer 6

标准方法（也许..？）只是检查从 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;
}

Answer 7

这是检查素数的有效方法。

 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;
    }

Answer 8

我认为这是一个更快的算法。它使用欧几里得算法来计算 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;
    }

如果我错了请纠正我。我是学生

如何以更有效的方式检查数字是否为素数？

How to check if a number is prime in a more efficient manner?

c++

primes