C++ 素数 Class

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.

这不是 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

判断一个数是否为质数，只需要检查小于被测数平方根的每个数除后的余数即可。此外，需要对小于或等于 1 的数字执行一些额外的检查。

bool isPrime(int x)
{
  if (x <= 1)
    return false;

  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0)
      return false;

  return true;
}

如果需要没有任何浮点计算和平方根的优化版本：

bool isPrime(int x)
{
  if (x <= 1)
    return false;
  if (x <= 3)
    return true;
  if (x % 2 == 0)
    return false;

  for (int i = 2; ; i += 2)
  {
    const auto result = std::div(x, i);
    if (result.rem == 0)
      return false;
    if (result.quot < i)
      return true;
  }

  return true;
}

Answer 2

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。

与其这样做（它要求您在递增实例时存储越来越多的质数），不如考虑（这往往是最简单的）。

编辑：改为考虑此算法：

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 提出的解决方案快得多（对于大量数据）。

结束编辑.

如果您正在寻找部分解决方案（几乎是素数，"probably prime" 的数字），请考虑 Rabin-Miller probabilistic primality test（或链接到该页面的其他测试）。

C++ 素数 Class

C++ PrimeNumber Class

c++

algorithm

primes