Класс C++ PrimeNumber
Вот проблема, которую я пытаюсь решить:
Определите класс с именем PrimeNumber, который хранит простое число. Конструктор по умолчанию должен установить простое число равным 1. Добавьте еще один конструктор, который позволяет вызывающему установить простое число. Кроме того, добавьте функцию, чтобы получить простое число. Наконец, перегрузите префикс и постфикс
++и-- operators, чтобы они возвращали объектPrimeNumber, который является следующим по величине простым числом (для++) и следующим по величине простым числом (для--). Например, если простое число объекта равно 13, то вызов++должен вернуть объектPrimeNumber, чье простое число равно 17. Создайте соответствующую тестовую программу для класса.
Это не для класса, я просто пытаюсь учить себя C++, потому что мне это нужно, так как я начну свою кандидатскую степень по финансовой математике в ФГУ этой осенью. Вот мой код до сих пор:
#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 я сначала говорю OK простые числа 2 и 3 являются простыми числами, а затем я исключаю любые числа, кратные 2 или 3. Что я хочу сделать, так это, возможно, создать цикл while, который устранит другие кратные числа, оставив только простые числа. Хотя я не совсем уверен, как этого достичь, если у кого-то есть какие-то предложения, я был бы очень признателен.
Теперь, когда об этом позаботились, я не могу заставить операторы ++ и -- работать правильно. Иногда это срабатывает, а иногда нет. нет.
2 ответов:
Алгоритм, который вы хотите применить, называетсярешетом Эратостена .Что я хочу сделать, это, возможно, создать цикл while, который исключил бы другие кратные числа, оставив только простые числа. Хотя я не совсем уверен, как этого достичь, если у кого-то есть какие-то предложения, я был бы очень признателен.
Вместо того, чтобы делать это (это потребовало бы, чтобы вы сохраняли все больше и больше простых чисел по мере увеличения экземпляра), рассмотрим алгоритм , предложенный Юраем Блахо (который, как правило, является самым простым).
Edit: вместо этого рассмотрим следующий алгоритм:
Это намного быстрее (для больших чисел), чем решение, предложенное Юраем Блахо.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; }Конец Редактирования .
Если вместо этого вы ищете частичные решения (почти простые числа, числа, которые "вероятно простые"), рассмотрите вероятностный тест на примитивность Рабина-Миллера (или другие тесты, связанные с этим страница).
Чтобы проверить, является ли число простым, вам просто нужно проверить остаток после деления каждого числа, меньшего квадратного корня из проверяемого числа. Кроме того, некоторые дополнительные проверки должны быть выполнены для чисел, меньших или равных 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; }
Comments