Multi-base primes: Difference between revisions
Content added Content deleted
m (C++ performance improvement) |
m (C++ performance improvement) |
||
Line 45: | Line 45: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|Primesieve}} |
|||
Originally translated from [[#Wren|Wren]] with ideas borrowed from other solutions. |
Originally translated from [[#Wren|Wren]] with ideas borrowed from other solutions. |
||
The maximum base and number of characters can be specified as command line arguments. |
The maximum base and number of characters can be specified as command line arguments. |
||
Line 55: | Line 56: | ||
#include <string> |
#include <string> |
||
#include <vector> |
#include <vector> |
||
#include <primesieve.hpp> |
|||
class prime_sieve { |
class prime_sieve { |
||
Line 67: | Line 69: | ||
}; |
}; |
||
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, |
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, false) { |
||
primesieve::iterator iter; |
|||
if (limit > 0) |
|||
uint64_t prime = iter.next_prime(); // consume 2 |
|||
sieve[0] = false; |
|||
while ((prime = iter.next_prime()) <= limit) { |
|||
sieve[prime >> 1] = true; |
|||
if (q >= limit) |
|||
break; |
|||
if (sieve[p >> 1]) { |
|||
uint64_t inc = 2 * p; |
|||
for (; q < limit; q += inc) |
|||
sieve[q >> 1] = false; |
|||
} |
|||
} |
} |
||
} |
} |
||
Line 180: | Line 175: | ||
{{out}} |
{{out}} |
||
Maximum base 36 and maximum length 6. This takes 0. |
Maximum base 36 and maximum length 6. This takes 0.41 seconds to process up to 5 character strings and 15 seconds to process up to 6 characters (3.2GHz Intel Core i5-4570). |
||
<pre> |
<pre> |
||
1-character strings which are prime in most bases: 34 |
1-character strings which are prime in most bases: 34 |
||
Line 205: | Line 200: | ||
</pre> |
</pre> |
||
Maximum base 62 and maximum length 5. This takes 0. |
Maximum base 62 and maximum length 5. This takes 0.15 seconds to process up to 4 character strings and 6.4 seconds to process up to 5 characters (3.2GHz Intel Core i5-4570). |
||
<pre> |
<pre> |
||
1-character strings which are prime in most bases: 60 |
1-character strings which are prime in most bases: 60 |