C++，确定素数

Question

我昨天开始读一本关于C++的书。到目前为止，我已经写了 100 页，并用这个数字来编写我的第一个程序。我想让它找出给定的数字是否是素数。

我有两个问题。

1. 我知道我的方法并不好。该程序正在检查每个数字，这使得程序变得很大。做到这一点的理想方法是什么？我是否理解你的答案并不重要，我稍后会简单地阅读命令:)。

2. 我的

   "Result+=1"

   线遇到了很大的问题。起初我有

   i=1

   ，这给了我以下数字

   7

   的结果。

   1111112

嗯，我也知道为什么。对于前 6 个 for 循环，他找到了一个数字

(1)

，对于最后一个

2(1,7)

，他找到了一个数字。但这显然不是我想要的。我希望 Result 成为某种计数器。我该怎么做？

代码：

#include <iostream>
using namespace std;



// Hauptprogramm

int main ()
{
    // Variablen
    int Prime_number;
    int Result = 0;

    // Abfragen
    cout << "Please enter possible prime number: ";
    cin >> Prime_number;

    // Rechnen
    for (int i=2; i <= Prime_number ; i++)
    {   
            if (Prime_number%i == 0)
            {   
                    Result +=1;
            }
    }

    // Ausgabe
    if(Result == 1)
    {
            cout << "You got a prime number!" << endl;
    }
    else
    {
            cout << "No luck" <<endl;
    }

    return 0;
}

Answer 1

你的逻辑很奇怪，而且正如你所说，效率很低。这是一个更好的逻辑

检查从 2 到 Prime_number - 1 的每个数字，如果其中任何一个能整除，那么它就不是素数，否则就是。重要的一点是，找到一个除数后就不再寻找，因为这样你就知道问题的答案了。这是一些执行此操作的代码

bool prime = true;
for (i = 2; i < Prime_Number; ++i)
{
    if (Prime_Number % i == 0)
    {
        prime = false;
        break;
    }
}
if (prime)
    cout << "You got a prime number!" << endl;
else
    cout << "No luck" <<endl;

我认为您在尝试中错过的两点是使用

bool

 变量，以及一旦知道循环完成就可以 

break

 退出循环。

顺便说一句，这段代码可以进一步改进，但这对你来说是一个练习。

Answer 2

下面的代码可以看到更有效的方法

#include<iostream>
#include<algorithm>
bool isprime(int a)
{
    int count=0;
    for(int i=2;i<sqrt(a);i++)
    {
        if(a%i==0)
        {count++;}
    }
    if(a==1||count!=0) return false;
    else return true;
}
int main()
{
  int a;
  cin>>a;
  if(isprime(a))
  {
    cout<<"number is prime";
  }
  else cout<<"number is not prime";
  return 0;
}

如您所见，这会成倍减少 isprime 函数中的测试用例数量，从而使代码更加高效。 希望这有帮助。

Answer 3

关于你的问题，我认为你的方法非常可靠：

为什么我从 i=2 开始？

我对素数的定义是一个有 2 个因数的数：1 和它本身。因此，当您从一个开始时，您（正确的）会计算一个额外的因子，因为 prime_number 可以被 1 整除。这会为您提供结果计数 2，因为它找到了两个因子。

有什么更好的方法吗？

有几种更好的方法，其中一些方法明显更复杂；然而，您现在拥有的算法可以通过几种直接方式轻松改进：

一旦发现任何既不是 1 也不是素数的因数 那么你就知道这个数字不是质数，只要有 (primenumber%i)==0 你可以设置一个像
• IsPrime=false 这样的标志并且 打破脱离循环。
即使对于质数，您也不需要真正达到质数，因为最大的因数可能是质数/2 - 因此您的循环速度将是原来的两倍，并且在这种情况下也能正常工作。 2.编辑：实际上，如果你想一下，素数的平方根是一个足够好的限制，因为所有因子都是成对出现的，并且较小的因子总是在这个限制内。

希望您学习愉快。

Answer 4

您也可以检查以下代码：

#include "time.h"
#include "iostream"
#include "conio.h"
using namespace std;

int main()
{
    div_t divresult;
    time_t t1,t2;   
    t1 = time(NULL); 
    int prime[1501] = {0};
    prime[1] = 2;
    prime[2] = 3;
    prime[3] = 5;
    prime[4] = 7;
    prime[5] = 11;
    int count = 6;

    for(int i = 12; count < 1500; i +=1)
    {
        bool Bprime = true; 
        for(int j = 1; j < count; j+=1)
        {
            if(i%prime[j] == 0) Bprime = false;
        }
        if(Bprime == true) prime[count++] = i;
    }
    t2 = time(NULL);
    divresult = div(t2-t1,60);
    cout<<divresult.quot <<" min "<<divresult.rem<<" sec"<<endl;
    int n = 0;
    cout<<"Give Value of N:";
    cin>> n;
    cout<<n<<"th prime is: "<<prime[n-1]<<endl;     

    _getch();
    return 0;
}

Answer 5

#include <stdio.h> 
#include <cmath>

bool BePrime(unsigned int N){
    if(N == 2) return true;

    for(int i = 2; i <= int(sqrt(N)); i++) {
        if(N%i == 0) return false;
    }
    return true;
}

main(){
    int a;
    while(scanf("%d",&a)){
        if(BePrime(a)) {
            printf("%d is Prime\n", a);
            continue;
        }
        printf("%d is not Prime\n", a);
    }

}

Answer 6

我认为这是一个简单的方法

> int main() {

int i = 2 , n, halfn;
cin>>n;
halfn = n / 2;

while(halfn > i) {
    if(n % i == 0) {
        cout << n << " Is NOT A Prime Number" << endl;
        break;
    }
    i++;
    if(halfn <= i ) {
        cout << n << " Is A Prime Number" << endl;
    }
}

return 0; }