Go back to Richel Bilderbeek's homepage.
Go back to Richel Bilderbeek's C++ page.
PrimeExpert is a class with only one important
member function called IsPrime,
which calculates whether a number is prime.
PrimeExpert is a trade-off between the speed of
determining whether a number is prime (for multiple times) and memory consumption:
to determine whether a number is prime quicker, PrimeExpert
maintains a std::vector of known primes (but of known primes only).
PrimeExpert can be tested using the tool
TestPrimeExpert.
Technical facts
primeexpert.h
//---------------------------------------------------------------------------
/*
PrimeExpert, class to calculate whether a number is prime
Copyright (C) 2008 Richel Bilderbeek
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//---------------------------------------------------------------------------
// From http://www.richelbilderbeek.nl/CppPrimeExpert.htm
//---------------------------------------------------------------------------
#ifndef PRIMEEXPERT_H
#define PRIMEEXPERT_H
//---------------------------------------------------------------------------
#include <string>
#include <vector>
//---------------------------------------------------------------------------
struct PrimeExpert
{
PrimeExpert();
bool IsPrime(const int x);
static const std::string GetVersion();
static const std::vector<std::string> GetVersionHistory();
private:
std::vector<int> mPrimes;
void CalculateNextPrime();
int CalculateMax(const int x);
friend std::ostream& operator<<(std::ostream&, const PrimeExpert&);
};
//---------------------------------------------------------------------------
std::ostream& operator<<(std::ostream& os, const PrimeExpert& primeExpert);
//---------------------------------------------------------------------------
#endif // PRIMEEXPERT_H
|
primeexpert.cpp
//---------------------------------------------------------------------------
/*
PrimeExpert, class to calculate whether a number is prime
Copyright (C) 2008 Richel Bilderbeek
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//---------------------------------------------------------------------------
// From http://www.richelbilderbeek.nl/CppPrimeExpert.htm
//---------------------------------------------------------------------------
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cassert>
#include "primeexpert.h"
//---------------------------------------------------------------------------
PrimeExpert::PrimeExpert()
{
mPrimes.push_back(2);
}
//---------------------------------------------------------------------------
void PrimeExpert::CalculateNextPrime()
{
const int heighestKnownPrime = mPrimes.back();
for (int i = heighestKnownPrime + 1; ;++i)
{
if (this->IsPrime(i)) { mPrimes.push_back(i); return; }
}
}
//------------------------------------------------------------
int PrimeExpert::CalculateMax(const int x)
{
return 1 + static_cast<int>(
std::sqrt(static_cast<double>(x) ) );
}
//---------------------------------------------------------------------------
const std::string PrimeExpert::GetVersion()
{
return "2.0";
}
//---------------------------------------------------------------------------
const std::vector<std::string> PrimeExpert::GetVersionHistory()
{
std::vector<std::string> v;
v.push_back("2008-07-12: Version 1.0: initial version in C++ Builder");
v.push_back("2011-02-26: Version 2.0: port to Qt Creator");
return v;
}
//---------------------------------------------------------------------------
bool PrimeExpert::IsPrime(const int x)
{
assert(x > 2);
//Calculate the maximum value for devision
const int max = CalculateMax(x);
assert(CalculateMax( 4) == 3); //When examining 4, divide (from 2) to 3
assert(CalculateMax( 5) == 3);
assert(CalculateMax( 6) == 3);
assert(CalculateMax( 7) == 3);
assert(CalculateMax( 8) == 3);
assert(CalculateMax( 9) == 4); //When examining 9, divide (from 2) to 4
assert(CalculateMax(10) == 4);
assert(CalculateMax(11) == 4);
assert(CalculateMax(12) == 4);
assert(CalculateMax(13) == 4);
assert(CalculateMax(14) == 4);
assert(CalculateMax(15) == 4);
assert(CalculateMax(16) == 5); //When examining 16, divide (from 2) to 5
assert(CalculateMax(17) == 5);
//Collect enough prime numbers to find if x is prime,
// if these are not yet present
while ( mPrimes.back() < CalculateMax(x) )
CalculateNextPrime();
for (int i=0; ;++i)
{
assert( i < static_cast<int>(mPrimes.size() ) );
const int knownPrime = mPrimes[i];
if (knownPrime >= max) return true;
if ( x % knownPrime == 0) return false;
}
}
//---------------------------------------------------------------------------
std::ostream& operator<<(std::ostream& os, const PrimeExpert& primeExpert)
{
std::copy(
primeExpert.mPrimes.begin(),
primeExpert.mPrimes.end(),
std::ostream_iterator<int>(os," ") );
return os;
}
//------------------------------------------------------------
|
Go back to Richel Bilderbeek's C++ page.
Go back to Richel Bilderbeek's homepage.
This page has been created by the tool CodeToHtml