Rosetta Code

Smarandache prime-digital sequence: Difference between revisions

Page Discussion

Smarandache prime-digital sequence (view source)

Revision as of 13:41, 8 July 2020

1,143 bytes removed ,  3 years ago
C++ code doesn't use a prime sieve (no benefit in this case)
(C code doesn't use a prime sieve (no benefit in this case))
(C++ code doesn't use a prime sieve (no benefit in this case))
Line 254:
<lang cpp>#include <iostream>
#include <cstdint>
#include "prime_sieve.hpp"
 
using integer = uint32_t;
Line 270 ⟶ 269:
return 2 + next_prime_digit_number(n/10) * 10;
}
}▼
 
bool is_prime(size_tinteger n) const;{▼
if (n ==< 2)▼
return false;▼
if (n < 2 || n % 2 == 0)▼
return truen == 2;▼
if (n % 3 == }0)▼
return n3n == n3;▼
for (size_tinteger p = 35; p * p <= limitn; p += 24) {▼
if (n % if (ip == 1000)▼
++ireturn false;▼
}p += 2;▼
if (n % n1p == n;0)▼
return n2 = nfalse;▼
}▼
return true;
}
 
int main() {
const integer limit = 10000000;
prime_sieve sieve(limit);
integer n = 0, n1 = 0, n2 = 0, n3 = 0;
std::cout << "First 25 SPDS primes:\n";
for (int i = 0; n < limit; ) {
n = next_prime_digit_number(n);
if (!is_prime(n >= limit))
breakcontinue;
if (sieve.is_prime(n)i < 25) {
if (i <> 250) {
ifstd::cout (i<< >", 0)";
std::cout << ", "n;
std::cout << n;▼
▲ }
else if (i == 25)▼
std::cout << '\n';▼
▲ ++i;
▲ if (i == 100)
▲ n1 = n;
else if (i == 1000)▼
▲ n2 = n;
▲ n3 = n;
}
▲ else if (i == 25)
▲ std::cout << '\n';
++i;
if (i == 100)
▲ n1 = std::cout << '\n';
▲ else if (i == 1000)
size_t incn2 = 2 * pn;▼
n3 = n;
}
std::cout << "Hundredth SPDS prime: " << n1 << '\n';
Line 302 ⟶ 315:
return 0;
}</lang>
 
Contents of prime_sieve.hpp:
<lang cpp>#ifndef PRIME_SIEVE_HPP
#define PRIME_SIEVE_HPP
 
#include <algorithm>
#include <vector>
 
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class prime_sieve {
public:
explicit prime_sieve(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 prime_sieve::prime_sieve(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 prime_sieve::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/290859"