Smarandache prime-digital sequence: Difference between revisions
Content added Content deleted
(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: | Line 254: | ||
<lang cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include <cstdint> |
#include <cstdint> |
||
#include "prime_sieve.hpp" |
|||
using integer = uint32_t; |
using integer = uint32_t; |
||
Line 270: | Line 269: | ||
return 2 + next_prime_digit_number(n/10) * 10; |
return 2 + next_prime_digit_number(n/10) * 10; |
||
} |
} |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
return true; |
|||
} |
} |
||
int main() { |
int main() { |
||
const integer limit = 10000000; |
const integer limit = 10000000; |
||
prime_sieve sieve(limit); |
|||
integer n = 0, n1 = 0, n2 = 0, n3 = 0; |
integer n = 0, n1 = 0, n2 = 0, n3 = 0; |
||
std::cout << "First 25 SPDS primes:\n"; |
std::cout << "First 25 SPDS primes:\n"; |
||
for (int i = 0; ; ) { |
for (int i = 0; n < limit; ) { |
||
n = next_prime_digit_number(n); |
n = next_prime_digit_number(n); |
||
if (n |
if (!is_prime(n)) |
||
continue; |
|||
if ( |
if (i < 25) { |
||
if (i |
if (i > 0) |
||
std::cout << ", "; |
|||
std::cout << n; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
⚫ | |||
⚫ | |||
++i; |
|||
if (i == 100) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
n3 = n; |
|||
} |
} |
||
std::cout << "Hundredth SPDS prime: " << n1 << '\n'; |
std::cout << "Hundredth SPDS prime: " << n1 << '\n'; |
||
Line 302: | Line 315: | ||
return 0; |
return 0; |
||
}</lang> |
}</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); |
|||
⚫ | |||
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 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 { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
return is_prime_.at(n/2 - 1); |
|||
} |
|||
#endif</lang> |
|||
{{out}} |
{{out}} |