summaryrefslogtreecommitdiff
path: root/proc/primes.c
diff options
context:
space:
mode:
Diffstat (limited to 'proc/primes.c')
-rw-r--r--proc/primes.c18
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));
-}
-