Multi-base primes: Difference between revisions
m
C++ performance improvement
(Added another Rust solution) |
m (C++ performance improvement) |
||
Line 56:
#include <vector>
public:
std::vector<bool> sieve(limit, true);▼
explicit prime_sieve(uint64_t limit);
bool is_prime(uint64_t n) const {
return n == 2 || ((n & 1) == 1 && sieve[n >> 1]);
}
private:
};
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, true) {
if (limit > 0)
sieve[0] = false;
for (uint64_t p = 3;; p += 2) {
uint64_t q = p * p;
if (q >= limit)
break;
if (sieve[p >> 1]) {
uint64_t inc = 2 * p;
for (; q < limit; q += inc)
sieve[q >> 1] = false;
}
}
}
Line 108 ⟶ 113:
void multi_base_primes(unsigned int max_base, unsigned int max_length) {
▲ prime_sieve(static_cast<uint64_t>(std::pow(max_base, max_length)));
for (unsigned int length = 1; length <= max_length; ++length) {
std::cout << length
Line 134 ⟶ 138:
for (auto d : digits)
n = n * b + d;
if (sieve
bases.push_back(b);
}
Line 176 ⟶ 180:
{{out}}
Maximum base 36 and maximum length 6. This takes 0.
<pre>
1-character strings which are prime in most bases: 34
Line 201 ⟶ 205:
</pre>
Maximum base 62 and maximum length 5. This takes 0.16 seconds to process up to 4 character strings and
<pre>
1-character strings which are prime in most bases: 60
| |||