On Thu, Jun 07, 2007 at 11:31:20PM +0200, Steinar H. Gunderson wrote:
> For comparison, a hastily coded version of the sieve of Eratosthenes
> finished in half a CPU second. A sieve of Atkin would probably be faster
> still.
FWIW, here's the (C99) program I used, for reference. I verified that it
generates correct results by commenting in the printfs and comparing against
the UNIX "primes" command.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#define MAX 10000000
bool field[MAX];
int main(void)
{
unsigned m = (int)(ceil(sqrt(MAX)));
unsigned num_primes = 0;
memset(field, 0, sizeof(field));
for (unsigned i = 2; i <= m; ++i) {
if (field[i])
continue;
++num_primes;
// printf("%u\n", i);
for (unsigned j = i * i; j < MAX; j += i)
field[j] = true;
}
for (unsigned i = m + 1; i < MAX; ++i) {
if (!field[i]) {
// printf("%u\n", i);
++num_primes;
}
}
printf("%u primes found.\n", num_primes);
}
/* Steinar */
--
Homepage: http://www.sesse.net/
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
