diff options
| -rw-r--r-- | proc/primes.c | 18 |
1 files changed, 7 insertions, 11 deletions
diff --git a/proc/primes.c b/proc/primes.c index 026349e7..65f4e5b8 100644 --- a/proc/primes.c +++ b/proc/primes.c @@ -1,4 +1,4 @@ -/* Seive of Eratosthenes +/* Prime number generation Copyright (C) 1994 Free Software Foundation This program is free software; you can redistribute it and/or @@ -31,6 +31,7 @@ nextprime (int n) if (!q) { + /* Init */ q = malloc (sizeof (int) * 2); q[0] = 2; q[1] = 3; @@ -41,14 +42,18 @@ nextprime (int n) while (n > q[l - 1]) { + /* Grow q */ + p = q[l-1] * q[l-1]; m = alloca (sizeof (int) * p); bzero (m, sizeof (int) * p); + /* Seive */ for (i = 0; i < l; i++) for (j = q[i] * 2; j < p; j += q[i]) m[j] = 1; + /* Copy */ for (i = q[l-1] + 1; i < p; i++) { if (l == k) @@ -61,6 +66,7 @@ nextprime (int n) } } + /* Binary search */ i = 0; j = l - 1; p = j / 2; @@ -78,13 +84,3 @@ nextprime (int n) } -main () -{ - int i; - - initprimes(); - - for (i = 0; i < 100; i++) - printf ("%d\t%d\n", i, nextprime(i)); -} - |