Smarandache prime-digital sequence: Difference between revisions
Content added Content deleted
m (Removed unnecessary #include) |
m (Updated Sieve of Eratosthenes C++ code) |
||
Line 365: | Line 365: | ||
#define SIEVE_OF_ERATOSTHENES_H |
#define SIEVE_OF_ERATOSTHENES_H |
||
#include <algorithm> |
|||
#include <vector> |
#include <vector> |
||
class sieve_of_eratosthenes |
class sieve_of_eratosthenes { |
||
{ |
|||
public: |
public: |
||
explicit sieve_of_eratosthenes(size_t); |
explicit sieve_of_eratosthenes(size_t); |
||
bool is_prime(size_t) const; |
bool is_prime(size_t) const; |
||
private: |
private: |
||
std::vector<bool> |
std::vector<bool> odd_prime_; |
||
}; |
}; |
||
inline bool sieve_of_eratosthenes::is_prime(size_t n) const |
inline bool sieve_of_eratosthenes::is_prime(size_t n) const { |
||
⚫ | |||
{ |
|||
return |
return true; |
||
if (n < 2 || n % 2 == 0) |
|||
⚫ | |||
return odd_prime_[n/2 - 1]; |
|||
} |
} |
||
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t |
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) { |
||
limit = std::max(size_t(3), 1 + 2*(limit/2)); |
|||
odd_prime_.resize((limit - 1)/2, true); |
|||
{ |
|||
⚫ | |||
is_prime_[0] = is_prime_[1] = false; |
|||
if (odd_prime_[p/2 - 1]) { |
|||
size_t inc = 2 * p; |
|||
{ |
|||
for (size_t q = p * p; q <= limit; q += inc) |
|||
odd_prime_[q/2 - 1] = false; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
} |
} |