这是我要解决的问题:
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 aPrimeNumber
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 aPrimeNumber
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 循环,以消除数字的其他倍数,只留下素数。虽然,我不确定如何实现这一目标,但如果有人有任何建议,我将不胜感激。
既然已经解决了,我似乎无法让++ 和 -- 运算符正常工作。有时有效,有时无效。
最佳答案
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 (或从该页面链接到的其他测试)。
关于C++ 素数类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30395230/