c++ - C++ PrimeNumber类

这是我要解决的问题:



这不是为了上课，我只是想自学C++，因为我需要它，因为我将于今年秋天在FSU开设金融数学博士学位。到目前为止，这是我的代码:

#include <iostream>
#include "PrimeNumber.h"
using namespace std;

int main() {
int x;
cout << "\nenter prime number: ";
cin >> x;

PrimeNumber p(x);
    PrimeNumber q(x);
p++;
    q--;
    cout << "\nprime before is " << q.GetPrime() << endl;
cout << "\nnext prime is " << p.GetPrime() << endl;

return 0;


}


class PrimeNumber {
int prime;
public:
PrimeNumber():prime(0){};
PrimeNumber(int num);
void SetPrime(int num);
int GetPrime(){return prime;};
PrimeNumber& operator++(int);
PrimeNumber& operator--(int);
static bool isPrime(int num);


};

void PrimeNumber::SetPrime(int num) {
if(isPrime(num)){
    prime = num;
}else{
    cout << num << " is not a prime Defaulting to 0.\n";
    prime = 0;
  }
 }

 PrimeNumber::PrimeNumber(int num){
  if(isPrime(num))
    prime = num;
  else {
    cout << num << " is not prime. Defaulting to 0.\n";
    prime = 0;
  }
 }


PrimeNumber& PrimeNumber::operator++(int){
//increment prime by 1 and test primality
//loop until a prime is found
do
{
    this->prime += 1;
}
while (! PrimeNumber::isPrime(this->prime));

}

PrimeNumber& PrimeNumber::operator--(int){
do
{
    this->prime -= 1;
}
while (!PrimeNumber::isPrime(this->prime));

}

bool PrimeNumber::isPrime(int num) {
if(num < 2)
    return false;

if(num == 2)
    return true;

if(num % 2 == 0)
    return false;

const int max_divisor = sqrt(num);
for(int div = 3; div < max_divisor; div += 2) // iterate odd numbers only
    if(num % div == 0)
        return false;
return true;
 }

因此，我的问题是，对于bool isPrime函数，我首先说好的2和3是质数，然后消除2或3的倍数的任何数字。我想做的也许是创建一个while循环，将消除数字的其他倍数而仅保留质数。尽管我不确定如何实现此目标，但是如果有人提出任何建议，我将不胜感激。

现在已经解决了，我似乎无法使++和-运算符正常工作。有时它起作用，有时却不起作用。

最佳答案

您要应用的算法称为Sieve of Erathostenes。

而不是这样做(这将要求您在增加实例时存储越来越多的质数)，而考虑使用algorithm proposed by Juraj Blaho(这通常是最简单的)。

编辑:请考虑以下算法:

bool PrimeNumber::isPrime(int num) {
    if(num < 2)
        return false;
    if(num == 2)
        return true;
    if(num % 2 == 0)
        return false;

    const int root = sqrt(num);
    for(int div = 3; div <= root; div += 2) // iterate odd numbers only
        if(num % div == 0)
            return false;
    return true;
}

(对于大量用户而言)这比Juraj Blaho提出的解决方案要快得多。

结束编辑。

如果您要查找部分解决方案(几乎是质数，即“可能是质数”的数字)，请考虑Rabin-Miller probabilistic primality test(或从该页面链接到的其他测试)。

关于c++ - C++ PrimeNumber类，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30395230/