Rosetta Code

Sequence of primorial primes: Difference between revisions

Page Discussion

Sequence of primorial primes (view source)

Revision as of 10:27, 10 June 2020

1,174 bytes removed ,  3 years ago
No need to use a prime sieve in C++ code
m (Minor edit to C++ code)
(No need to use a prime sieve in C++ code)
Line 99:
#include <sstream>
#include <gmpxx.h>
#include "sieve_of_eratosthenes.h"
 
typedef mpz_class integer;
 
bool is_primeis_probably_prime(const integer& n) {
return mpz_probab_prime_p(n.get_mpz_t(), 25) != 0;
}▼
 
bool is_prime(unsigned int n) {
if (n ==< 2)▼
return false;▼
if (n < 2 || n % 2 == 0)▼
return truen == 2;▼
if (n % 3 }== 0)▼
return n == 3;
for (size_tunsigned int p = 35; p * p <= limitn; p += 24) {▼
if (is_prime_[n % p/2 -== 1]0) {▼
size_treturn inc = 2 * pfalse;▼
p += 2;
if (n % p == 0)
is_prime_[q/2 - 1] =return false;▼
}▼
return true;
}
 
int main() {
const size_t max_prime = 4000;
const size_t max = 20;
sieve_of_eratosthenes sieve(max_prime);
integer primorial = 1;
for (size_t p = 0, count = 0, index = 0; p < max_prime && count < max; ++p) {
if (!sieve.is_prime(p))
continue;
primorial *= p;
++index;
if (is_primeis_probably_prime(primorial - 1) || is_primeis_probably_prime(primorial + 1)) {
if (count > 0)
std::cout << ' ';
Line 127 ⟶ 141:
return 0;
}</lang>
 
Contents of sieve_of_eratosthenes.h:
<lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H
#define SIEVE_OF_ERATOSTHENES_H
 
#include <algorithm>
#include <vector>
 
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class sieve_of_eratosthenes {
public:
explicit sieve_of_eratosthenes(size_t);
bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
 
/**
* Constructs a sieve with the given limit.
*
* @param limit the maximum integer that can be tested for primality
*/
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) {
limit = std::max(size_t(3), limit);
is_prime_.resize(limit/2, true);
▲ for (size_t p = 3; p * p <= limit; p += 2) {
▲ if (is_prime_[p/2 - 1]) {
▲ size_t inc = 2 * p;
for (size_t q = p * p; q <= limit; q += inc)
▲ is_prime_[q/2 - 1] = false;
▲ }
▲ }
▲}
 
/**
* Returns true if the given integer is a prime number. The integer
* must be less than or equal to the limit passed to the constructor.
*
* @param n an integer less than or equal to the limit passed to the
* constructor
* @return true if the integer is prime
*/
inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
▲ if (n == 2)
▲ return true;
▲ if (n < 2 || n % 2 == 0)
▲ return false;
return is_prime_.at(n/2 - 1);
}
 
#endif</lang>
 
{{out}}
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/259407"