C++ 素数类

Question

这是我要解决的问题:

Define a class named PrimeNumber that stores a prime number. The default constructor should set the prime number to 1. Add another constructor that allows the caller to set the prime number. Also, add a function to get the prime number. Finally, overload the prefix and postfix ++ and -- operators so they return a PrimeNumber object that is the next largest prime number (for ++) and the next smallest prime number (for --). For example, if the object's prime number is set to 13, then invoking ++ should return a PrimeNumber object whose prime number is set to 17. Create an appropriate test program for the class.

这不是为了上课，我只是想自学 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 循环，以消除数字的其他倍数，只留下素数。虽然，我不确定如何实现这一目标，但如果有人有任何建议，我将不胜感激。

既然已经解决了，我似乎无法让++ 和 -- 运算符正常工作。有时有效，有时无效。

Answer 1

What I want to do is perhaps create a while loop that would eliminate the other multiples of the number leaving the prime numbers only. Although, I am not exactly sure how to achieve this, if anyone has any suggestions, I would greatly appreciate it.

您要应用的算法称为 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 (或从该页面链接到的其他测试)。