Multi-base primes: Difference between revisions

Line 45:

=={{header|C++}}==

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.

Line 55:

Line 56:

#include <string>

#include <vector>

#include <primesieve.hpp>

class prime_sieve {

Line 67:

Line 69:

};

prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, ~~true~~) {

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;

~~for~~ (~~uint64_t p~~ = ~~3;; p~~ += 2) {

while ((prime = iter.next_prime()) <= limit) {

~~uint64_t~~ q = ~~p * p~~;

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:

Maximum base 36 and maximum length 6. This takes 0.5 seconds to process up to 5 character strings and 23 seconds to process up to 6 characters (3.2GHz Intel Core i5-4570).

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>

1-character strings which are prime in most bases: 34

Line 205:

Line 200:

</pre>

Maximum base 62 and maximum length 5. This takes 0.16 seconds to process up to 4 character strings and 10 seconds to process up to 5 characters (3.2GHz Intel Core i5-4570).

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>

1-character strings which are prime in most bases: 60