Sexy primes: Difference between revisions
m
Put Sieve of Eratosthenes implementation in separate header file
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
m (Put Sieve of Eratosthenes implementation in separate header file) |
||
Line 304:
</pre>
=={{header|C++}}==
<lang cpp>#include <iostream>
#include <iostream>▼
#include <vector>
#include "sieve_of_eratosthenes.h"
int main()
Line 322:
// Use Sieve of Eratosthenes to find prime numbers up to max
for (int p = 2; p * p < array_size; ++p)▼
{▼
if (isprime[p])▼
{▼
for (int i = p * p; i < array_size; i += p)▼
isprime[i] = false;▼
}▼
}▼
vector<int> group_count(max_group_size);
Line 339 ⟶ 331:
for (int p = 2; p < max; )
{
if (!
{
// if p + diff and p - diff aren't prime then p can't be sexy
Line 356 ⟶ 348:
{
int next_p = p + i * diff;
if (next_p >= max || !
break;
++group_size;
Line 370 ⟶ 362:
// skip to next prime number
++p;
while (p < max && !
++p;
}
Line 399 ⟶ 391:
return 0;
}</lang>▼
Contents of sieve_of_eratosthenes.h:
<lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H
#define SIEVE_OF_ERATOSTHENES_H
class sieve_of_eratosthenes
{
public:
explicit sieve_of_eratosthenes(size_t);
bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
inline bool sieve_of_eratosthenes::is_prime(size_t n) const
{
return is_prime_[n];
}
▲</lang>
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t max)
: is_prime_(max, true)
{
is_prime_[0] = is_prime_[1] = false;
▲ {
▲ {
▲ }
▲ }
}
#endif</lang>
{{out}}
|