Extensible prime generator
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Write a generator of prime numbers, in order, that will automatically adjust to accommodate the generation of any reasonably high prime.
The routine should demonstrably rely on either:
- Being based on an open-ended counter set to count without upper limit other than system or programming language limits. In this case, explain where this counter is in the code.
- Being based on a limit that is extended automatically. In this case, choose a small limit that ensures the limit will be passed when generating some of the values to be asked for below.
- If other methods of creating an extensible prime generator are used, the algorithm's means of extensibility/lack of limits should be stated.
The routine should be used to:
- Show the first twenty primes.
- Show the primes between 100 and 150.
- Show the number of primes between 7,700 and 8,000.
- Show the 10,000th prime.
Show output on this page.
Note: You may reference code already on this site if it is written to be imported/included, then only the code necessary for import and the performance of this task need be shown. (It is also important to leave a forward link on the referenced tasks entry so that later editors know that the code is used for multiple tasks).
Note 2: If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a system limit, (2^{31} or memory overflow for example), then this may be used as long as an explanation of the limits of the prime generator is also given. (Which may include a link to/excerpt from, language documentation).
- See also
- The task is written so it may be useful in solving task Emirp primes as well as others (depending on its efficiency).
Contents
Ada[edit]
The solution is based on an open-ended counter, named "Current" counting up to the limit from the Compiler, namely 2**63-1.
The solution uses the package Miller_Rabin from the Miller-Rabin primality test. When using the gnat Ada compiler, the largest integer we can deal with is 2**63-1. For anything larger, we could use a big-num package.
with Ada.Text_IO, Miller_Rabin;
procedure Prime_Gen is
type Num is range 0 .. 2**63-1; -- maximum for the gnat Ada compiler
MR_Iterations: constant Positive := 25;
-- the probability Pr[Is_Prime(N, MR_Iterations) = Probably_Prime]
-- is 1 for prime N and < 4**(-MR_Iterations) for composed N
function Next(P: Num) return Num is
N: Num := P+1;
package MR is new Miller_Rabin(Num); use MR;
begin
while not (Is_Prime(N, MR_Iterations) = Probably_Prime) loop
N := N + 1;
end loop;
return N;
end Next;
Current: Num;
Count: Num := 0;
begin
-- show the first twenty primes
Ada.Text_IO.Put("First 20 primes:");
Current := 1;
for I in 1 .. 20 loop
Current := Next(Current);
Ada.Text_IO.Put(Num'Image(Current));
end loop;
Ada.Text_IO.New_Line;
-- show the primes between 100 and 150
Ada.Text_IO.Put("Primes between 100 and 150:");
Current := 99;
loop
Current := Next(Current);
exit when Current > 150;
Ada.Text_IO.Put(Num'Image(Current));
end loop;
Ada.Text_IO.New_Line;
-- count primes between 7700 and 8000
Ada.Text_IO.Put("Number of primes between 7700 and 8000:");
Current := 7699;
loop
Current := Next(Current);
exit when Current > 8000;
Count := Count + 1;
end loop;
Ada.Text_IO.Put_Line(Num'Image(Count));
Count := 10;
Ada.Text_IO.Put_Line("Print the K_i'th prime, for $K=10**i:");
begin
loop
Current := 1;
for I in 1 .. Count loop
Current := Next(Current);
end loop;
Ada.Text_IO.Put(Num'Image(Count) & "th prime:" &
Num'Image(Current));
Count := Count * 10;
end loop;
exception
when Constraint_Error =>
Ada.Text_IO.Put_Line(" can't compute the" & Num'Image(Count) &
"th prime:");
end;
end;
- Output:
First 20 primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Primes between 100 and 150: 101 103 107 109 113 127 131 137 139 149 Number of primes between 7700 and 8000: 30 Print the K_i'th prime, for $K=10**i: 10th prime: 29 100th prime: 541 1000th prime: 7919 10000th prime: 104729 100000th prime: 1299709 1000000th prime: 15485863
(The program has been stopped after running several days.)
AutoHotkey[edit]
SetBatchLines, -1
p := 1 ;p functions as the counter
Loop, 10000 {
p := NextPrime(p)
if (A_Index < 21)
a .= p ", "
if (p < 151 && p > 99)
b .= p ", "
if (p < 8001 && p > 7699)
c++
}
MsgBox, % "First twenty primes: " RTrim(a, ", ")
. "`nPrimes between 100 and 150: " RTrim(b, ", ")
. "`nNumber of primes between 7,700 and 8,000: " RTrim(c, ", ")
. "`nThe 10,000th prime: " p
NextPrime(n) {
Loop
if (IsPrime(++n))
return n
}
IsPrime(n) {
if (n < 2)
return, 0
else if (n < 4)
return, 1
else if (!Mod(n, 2))
return, 0
else if (n < 9)
return 1
else if (!Mod(n, 3))
return, 0
else {
r := Floor(Sqrt(n))
f := 5
while (f <= r) {
if (!Mod(n, f))
return, 0
if (!Mod(n, (f + 2)))
return, 0
f += 6
}
return, 1
}
}
- Output:
First twenty primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 Primes between 100 and 150: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 Number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729
C[edit]
Extends the list of primes by sieving more chunks of integers. There's no serious optimizations. The code can calculate all 32-bit primes in some seconds, and will overflow beyond that.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define CHUNK_BYTES (32 << 8)
#define CHUNK_SIZE (CHUNK_BYTES << 6)
int field[CHUNK_BYTES];
#define GET(x) (field[(x)>>6] & 1<<((x)>>1&31))
#define SET(x) (field[(x)>>6] |= 1<<((x)>>1&31))
typedef unsigned uint;
typedef struct {
uint *e;
uint cap, len;
} uarray;
uarray primes, offset;
void push(uarray *a, uint n)
{
if (a->len >= a->cap) {
if (!(a->cap *= 2)) a->cap = 16;
a->e = realloc(a->e, sizeof(uint) * a->cap);
}
a->e[a->len++] = n;
}
uint low;
void init(void)
{
uint p, q;
unsigned char f[1<<16];
memset(f, 0, sizeof(f));
push(&primes, 2);
push(&offset, 0);
for (p = 3; p < 1<<16; p += 2) {
if (f[p]) continue;
for (q = p*p; q < 1<<16; q += 2*p) f[q] = 1;
push(&primes, p);
push(&offset, q);
}
low = 1<<16;
}
void sieve(void)
{
uint i, p, q, hi, ptop;
if (!low) init();
memset(field, 0, sizeof(field));
hi = low + CHUNK_SIZE;
ptop = sqrt(hi) * 2 + 1;
for (i = 1; (p = primes.e[i]*2) < ptop; i++) {
for (q = offset.e[i] - low; q < CHUNK_SIZE; q += p)
SET(q);
offset.e[i] = q + low;
}
for (p = 1; p < CHUNK_SIZE; p += 2)
if (!GET(p)) push(&primes, low + p);
low = hi;
}
int main(void)
{
uint i, p, c;
while (primes.len < 20) sieve();
printf("First 20:");
for (i = 0; i < 20; i++)
printf(" %u", primes.e[i]);
putchar('\n');
while (primes.e[primes.len-1] < 150) sieve();
printf("Between 100 and 150:");
for (i = 0; i < primes.len; i++) {
if ((p = primes.e[i]) >= 100 && p < 150)
printf(" %u", primes.e[i]);
}
putchar('\n');
while (primes.e[primes.len-1] < 8000) sieve();
for (i = c = 0; i < primes.len; i++)
if ((p = primes.e[i]) >= 7700 && p < 8000) c++;
printf("%u primes between 7700 and 8000\n", c);
for (c = 10; c <= 100000000; c *= 10) {
while (primes.len < c) sieve();
printf("%uth prime: %u\n", c, primes.e[c-1]);
}
return 0;
}
- Output:
First 20: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 30 primes between 7700 and 8000 10th prime: 29 100th prime: 541 1000th prime: 7919 10000th prime: 104729 100000th prime: 1299709 1000000th prime: 15485863 10000000th prime: 179424673 100000000th prime: 2038074743
Clojure[edit]
ns test-project-intellij.core
(:gen-class)
(:require [clojure.string :as string]))
(def primes
" The following routine produces a infinite sequence of primes
(i.e. can be infinite since the evaluation is lazy in that it
only produces values as needed). The method is from clojure primes.clj library
which produces primes based upon O'Neill's paper:
'The Genuine Sieve of Eratosthenes'.
Produces primes based upon trial division on previously found primes up to
(sqrt number), and uses 'wheel' to avoid
testing numbers which are divisors of 2, 3, 5, or 7.
A full explanation of the method is available at:
[https://github.com/stuarthalloway/programming-clojure/pull/12] "
(concat
[2 3 5 7]
(lazy-seq
(let [primes-from ; generates primes by only checking if primes
; numbers which are not divisible by 2, 3, 5, or 7
(fn primes-from [n [f & r]]
(if (some #(zero? (rem n %))
(take-while #(<= (* % %) n) primes))
(recur (+ n f) r)
(lazy-seq (cons n (primes-from (+ n f) r)))))
; wheel provides offsets from previous number to insure we are not landing on a divisor of 2, 3, 5, 7
wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2
6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6
2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
(primes-from 11 wheel)))))
(defn between [lo hi]
"Primes between lo and hi value "
(->> (take-while #(<= % hi) primes)
(filter #(>= % lo))
))
(println "First twenty:" (take 20 primes))
(println "Between 100 and 150:" (between 100 150))
(println "Number between 7,7700 and 8,000:" (count (between 7700 8000)))
(println "10,000th prime:" (nth primes (dec 10000))) ; decrement by one since nth starts counting from 0
}
- Output:
First 20: (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) Between 100 and 150: (101 103 107 109 113 127 131 137 139 149) Number between 7,700 and 8,000: 30 10000th prime: 104729
D[edit]
This uses a Prime struct defined in the third entry of the Sieve of Eratosthenes task. Prime keeps and extends a dynamic array instance member of uints. The Prime struct has a opCall that returns the n-th prime number. The opCall calls a grow() private method until the dynamic array of primes is long enough to contain the required answer. The function grow() just grows the dynamic array geometrically and performs a normal sieving. On a 64 bit system this program works up to the maximum prime number that can be represented in the 32 bits of an uint. This program is less efficient than the C entry, so it's better to not use it past some tens of millions of primes, but it's enough for more limited usages.
void main() {
import std.stdio, std.range, std.algorithm, sieve_of_eratosthenes3;
Prime prime;
writeln("First twenty primes:\n", 20.iota.map!prime);
writeln("Primes primes between 100 and 150:\n",
uint.max.iota.map!prime.until!q{a > 150}.filter!q{a > 99});
writeln("Number of primes between 7,700 and 8,000: ",
uint.max.iota.map!prime.until!q{a > 8_000}
.filter!q{a > 7_699}.walkLength);
writeln("10,000th prime: ", prime(9_999));
}
- Output:
First twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] Primes primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] Number of primes between 7,700 and 8,000: 30 10,000th prime: 104729
Faster Alternative Version[edit]
/// Prime sieve based on: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
import std.container: Array, BinaryHeap, RedBlackTree;
struct LazyPrimeSieve {
@property bool empty() const pure nothrow @safe @nogc {
return i > 203_280_221; // Pi(2 ^^ 32).
}
@property auto front() const pure nothrow @safe @nogc {
return prime;
}
@property void popFront() pure nothrow [email protected]*/ {
prime = sieveOne();
}
private:
static struct Wheel2357 {
static immutable ubyte[48] holes = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6,
2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10];
static immutable ubyte[4] spokes = [2, 3, 5, 7];
static immutable ubyte first = 11;
uint i;
auto spin() pure nothrow @safe @nogc {
return holes[i++ % $];
}
}
static struct CompositeIterator {
uint prime;
Wheel2357 wheel;
ulong composite;
this(uint p) pure nothrow @safe @nogc {
prime = p;
composite = p * wheel.first;
}
void next() pure nothrow @safe @nogc {
composite += prime * wheel.spin;
}
}
version (heap) // Less memory but slower.
BinaryHeap!(Array!CompositeIterator, "a.composite > b.composite") iterators;
else // Faster but is more GC intensive.
RedBlackTree!(CompositeIterator, "a.composite < b.composite", true) iterators;
uint prime = 2;
uint i = 1;
Wheel2357 wheel;
uint candidate = wheel.first;
uint sieveOne() pure nothrow [email protected]*/ {
switch (i) {
case 0: .. case wheel.spokes.length - 1:
return wheel.spokes[i++];
case wheel.spokes.length:
i++;
return candidate;
case wheel.spokes.length + 1:
version (heap) {}
else
iterators = new typeof(iterators);
goto default;
default:
goto POST_RETURN;
while (true) {
candidate += wheel.spin;
while (iterators.front.composite < candidate) {
auto it = iterators.front;
iterators.removeFront;
it.next;
iterators.insert(it);
}
if (iterators.front.composite != candidate) {
i++;
return candidate;
POST_RETURN:
// Only insert primes that are multiply
// occuring in [0, 2 ^^ 32).
if (candidate < 2 ^^ 16)
iterators.insert(CompositeIterator(candidate));
}
}
}
}
}
void main() [email protected]*/ {
import std.stdio, std.algorithm, std.range;
writeln("Sum of first 100,000 primes: ", LazyPrimeSieve().take(100_000).sum(0uL));
writeln("First twenty primes:\n", LazyPrimeSieve().take(20));
writeln("Primes primes between 100 and 150:\n",
LazyPrimeSieve().until!q{a > 150}.filter!q{a > 99});
writeln("Number of primes between 7,700 and 8,000: ",
LazyPrimeSieve().until!q{a > 8_000}.filter!q{a > 7_699}.walkLength);
writeln("10,000th prime: ", LazyPrimeSieve().dropExactly(9999).front);
}
- Output:
Sum of first 100,000 primes: 62260698721 First twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] Primes primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] Number of primes between 7,700 and 8,000: 30 10,000th prime: 104729
EchoLisp[edit]
Standard prime functions handle numbers < 2e+9. See [1] . The bigint library handles large numbers. See [2]. The only limitations are time, memory, and browser performances ..
; the first twenty primes
(primes 20)
→ { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 }
; a stream to generate primes from a
(define (primes-from a)
(let ((p (next-prime a)))
(stream-cons p (primes-from p))))
; primes between 100,150
(for/list ((p (primes-from 100))) #:break (> p 150) p)
→ (101 103 107 109 113 127 131 137 139 149)
; the built-in function (primes-pi )counts the number of primes < a
; count in [7700 ... 8000]
(- (primes-pi 8000) (primes-pi 7700) → 30
; nth-prime
(nth-prime 10000) → 104729
;; big ones
(lib 'bigint)
(define (p-digits n)
(printf "(next-prime %d ! ) has %d digits" n
(number-length (next-prime (factorial n )))))
(next-prime 0! ) has 1 digits
(next-prime 10! ) has 7 digits
(next-prime 100! ) has 158 digits
(next-prime 200! ) has 375 digits
(next-prime 300! ) has 615 digits
(next-prime 400! ) has 869 digits ;; 9400 msec (FireFox)
; is prime (1 + 116!) ?
(prime? (1+ (factorial 116))) → #t
Fortran[edit]
The Plan[edit]
Over the years, the storage of boolean variables has been a steady source of vexation. Few systems offer operation codes that can work on individual bits, so the usual approach is to allocate a convenient storage unit to hold the value. In Fortran, the default size of a LOGICAL variable is the same as that of an INTEGER variable, and these days, that means thirty-two bits to store the state of one. However, with the increasing use of character manipulation rather than just numbers, there is often support in the cpu for single-character access and some later Fortran compilers will recognise LOGICAL*1 and so reserve only eight bits per boolean variable. Even so, any attempt to store a boolean variable in a single bit will for every access require code to isolate that bit from the rest of the storage unit where it resides, and these operation codes will require more storage than would be saved. Similarly with collections of variables: some might best be aligned to word boundaries (and for double-sized variables, perhaps to even word boundaries) so the storage plan may well involve adding "padding" to preserve such alignment. Some languages (such as pl/i) offer a word ALIGNED to ensure this, and others (such as Pascal) offer PACKED for cramming, of use when dealing with records for a disc file and intending to save space. So, ... if there is a large array of boolean variables, and, there are not so many references to those variables, there is still an opportunity.
And indeed, the array shall be large. Some simple investigations show that storing a collection of prime numbers in an array of integers occupies rather more storage than storing a simple bit array spanning the same range of numbers, and given the obvious scheme of storing bits only for odd integers, this advantage is still greater - see the schedule in the source file. One could argue that the array of successive prime numbers could be stored in various space-saving ways, but, so also can the bit array be compressed. For instance, have a span of a "primorial" size such as 2*3*5 and a reference span with those factors marked "off": that removes seven odd numbers from consideration, leaving eight candidates for each surge and so only eight bits are required to state "prime" or not instead of fifteen. With non-binary computers, "bit fiddling" is less convenient but still possible. One must use techniques similar to those needed to work with the year, month, and day parts of an integer such as 20161015 in binary.
So, the plan is to have a long array of bits, and, rather than commit a lot of memory to this, do so in a disc file with random access. To follow the "extensible" aspect, this disc file will not be initialised to its maximum extent on the first invocation of the routine, instead, it will be extended as provoked by requests for NEXTPRIME and so forth.
Initialisation[edit]
When arranging a sieve of Eratosthenes, one of the problems is that one wishes to step along only with steps of prime number size to avoid wasted effort, but, before the sieve process is completed, there is no ready source of known prime numbers. This is especially difficult when instead of one long sieve covering the whole span of interest, the process is to proceed in surges, repeatedly using some limited size span. For this reason, it is often convenient to prepare an initial array of prime numbers knowing for example that Prime(4792) = 46337, and that the square of the next prime exceeds the range of signed 32-bit integers. But such pre-emptive preparation conflicts with the "extensible" notion, and requires special code and storage for the array.
Because Fortran passes parameters by reference (i.e. by address of the original) a trick is possible. The array SCHARS is shared storage to hold a record from the disc file (as a "buffer") and when subroutine GRASPPRIMEBAG is invoked to gain access to its disc file it notes whether it must create the file. If so, the first record is to be written, and the call is PSURGE(SCHARS) to do so within the shared bitpad. PSURGE knows that its first stepper is with F = 3
(because even numbers are not being represented) and proceeds with that, adjusting array SCHARS. When it is ready for the next sieve pass, it invokes F = NEXTPRIME(F)
to find the next stepper, which will be five, and NEXTPRIME scans the bit array in SCHARS to find it. This is the same bitpad that PSURGE is in the process of adjusting. To support this startup ploy, GETSREC (invoked by NEXTPRIME) returns at once when SLAST = 0, signifying that there are no records in the work file as yet. Later, if GETSREC determines that the bit array is to be extended, it invokes PSURGE with its local array BIT8 as the bitpad to be developed then written to disc, leaving the shared SCHAR array as a record buffer for the use of NEXTPRIME when invoked by PSURGE.
Supporting NextPrime(n)[edit]
Since the bit array has a simple linear relationship to the numbers it is associated with, function NEXTPRIME(n)
(and PREVIOUSPRIME(n)
) can easily calculate the index to access the appropriate bits; similarly, function ISPRIME(n)
need merely check n = NEXTPRIME(n - 1)
rather than slog through possibly all potential prime factors up to SQRT(n) - though this does mean that prime numbers up to n must be available rather than merely up to SQRT(n). But there would be no escape from such a slog for function FIRSTFACTOR(n), unless one abandoned the bit array for a FF array and modified the sieve process to record the first factor. Something like Bit(i) = .false.
would be replaced by if (FF(i) <= 1) then FF(i) = F
Were the assignment to be made unconditionally (for faster running, perhaps), the array should be renamed to MaximumPrimeFactor. Either way, ISPRIME(n) remains easy, but much more storage than one bit per entry would be required.
If instead of the next prime one desires to find the n 'th prime number, then there is a difficulty that would not exist if the prime numbers only were stored in an array - though then NEXTPRIME(n)
would have difficulty. Of course, if storage is abundant, both forms of storage could be used and each request could be handled via a simple linear index calculation into the appropriate array.
Supporting Prime(n)[edit]
To find the n'th prime number, obviously one could scan along the bit array from the start, keeping count. This will soon become tedious, so in order to support function PRIME(n)
, each record starts with a count of all the primes that have preceded that record's span and so to find the count for a prime fingered in that record, the scan need work only from the start of that record. So the problem reduces to determining which record is the one containing the n 'th prime. Since the counts are obviously strictly increasing, a binary search would be a possibility as would be an interpolating search and one could even prepare an array containing the counts so that the search could proceed without needing disc accesses - at the cost of additional storage and organisational complexity, perhaps involving Aitken's interpolation formula, except that polynomials do not provide a good fit to the required shape. Fortunately, mathematicians have considered this aspect of prime numbers also, and a rather intimidating formula is available to give an estimate of the value of the n 'th prime number. Equipped with this, the appropriate record can be read, the count inspected, and a scan started to find the actual n 'th prime. Function PRIME(n)
can be invoked just as array PRIME(n)
might be, but with something of a roil of activity in the background.
Preparing the count field involves another trick, because the first record's count field instead holds the count of records in the bit file. Now note that the sieve starts with SORG = 3
which means that before the first block there is a count of one prime number. Thus, if function PRIME is accessing the first block, it must know that the count of previous primes is one and not refer to the count field which instead holds the record count. When PSURGE is preparing the next batch of bits (for the second and subsequent records) it accesses the previous record to find the previous count and scans that record to count its primes so as to prepare the previous count for the new record. When the second record is being prepared by PSURGE, the previous record (the first record) has a record count of one, and, this is exactly the desired count of previous primes for the first record. But only at this point, because in moments the first record will be rewritten with a record count of two. For all this to work, SORG = 3
must be the case: it is not a parameter but a constant.
Integer Overflow[edit]
The variables are all the default thirty-two bit two's complement integers and integer overflow is a possibility, especially because someone is sure to wonder what is the largest prime that can be represented in thirty-two bits - see the output. The code would be extensible in another way, if all appearances of INTEGER
were to be replaced by INTEGER*8
though not all variables need be changed - such as C
and B
because they need only index a character in array SCHARS or a bit in a character. Using sixty-four bits for such variables is excessive even if the cpu uses a 64-bit data bus to memory. If such a change were to be made, then all would go well as cpu time and disc space were consumed up to the point when the count of prime numbers can no longer be fitted into the four character storage allowance in the record format. This will be when more than 4,294,967,295 primes have been counted (with 64-bit arithmetic its four bytes will manifest as an unsigned integer) in previous records, and Prime(4,294,967,295) = 104,484,802,043, so that the bit file would require a mere 6,530MB or so - which some may think is not too much. If so, expanding the allowance from four to five characters would be easy enough, and then 256 times as many primes could be counted. That would also expand the reach of the record counter, which otherwise would be limited to 4,294,967,295 records of 4096 bytes each, or a bit bag of 17,592,186,040,320 bytes - only seventeen terabytes...
LST
is the number corresponding to the last bit of the current span, DO WHILE(F*F <= LST) !But, F*F might overflow the integer limit so instead,
DO WHILE(F <= LST/F) !Except, LST might also overflow the integer limit, so
DO WHILE(F <= (IST + 2*(SBITS - 1))/F) !Which becomes...
DO WHILE(F <= IST/F + (MOD(IST,F) + 2*(SBITS - 1))/F) !Preserving the remainder from IST/F.
Except, IST
might overflow the integer limit, in which case function PSURGE declares itself unable to proceed and returns false.
Overflow is detected by the sudden appearance of negative numbers, as is characteristic of two's complement integer arithmetic. This is not guaranteed to be used on all computers (notably, on a decimal computer such as the IBM1620 and others), and in its absence, the procedure will malfunction. Some systems detect integer overflow via hardware (a special "flag" register, or an interrupt) and there may be facilities for noticing such events. First Fortran (1957) offered special statements such as IF ACCUMULATOR OVERFLOW labelon,labeloff
(yes, without brackets) and similarly for QUOTIENT OVERFLOW and DIVIDE CHECK but they were abandoned by the modernisers. The only general solution to this problem would be to convert to using multiple-precision (or "bignum") arithmetic, whereupon the code becomes extensible in another way simply by extending as needed the amount of storage allowed for variables.
These methods have been tested by converting INTEGER
to INTEGER*2
and also by using a record size of sixteen bytes (because UltraEdit, when displaying in binary, shows that many bytes to a line), and it was a real pleasure for once to be able to read the 32-bit count field at the start of each record left-to-right in hexadecimal rather than in the crazed little-endian order that would otherwise have been used.
The Code[edit]
The source code employs the MODULE facility of F90 simply to avoid the tedium of setting up a COMMON storage area and having to declare the type of the functions in every routine that uses them. Otherwise, older style compilers will accept this, except for an occasional array facility (such as BIT8 = CHAR(255)
) and the use of the $ format code to allow the next output to tag on to the same line. The rather more fearsome declaration RECURSIVE FUNCTION NEXTPRIME
could be avoided if in subroutine PSURGE, the invocation of NEXTPRIME was replaced by in-line code. Similarly with subroutine GETSREC, though forgetting this didn't seem to make any difference. This is just convenience recursion, not structural recursion to some arbitrary depth.
Although recursion is now permissible if one utters the magic word RECURSIVE
, this ability usually is not extended to the workings for formatted I/O so that if say a function is invoked in a WRITE statement's list, should that function attempt to use a WRITE statement, the run will be stopped. There can be slight dispensations if different types of WRITE statement are involved (say, formatted, and "free"-format) but an ugly message is the likely result. The various functions are thus best invoked via an assignment statement to a scratch variable, which can then be printed. The functions are definitely not "pure" because although they are indeed functions only of their arguments, they all mess with shared storage, can produce error messages (and even a STOP), and can provoke I/O with a disc file, even creating such a file. For this reason, it would be unwise to attempt to invoke them via any sort of parallel processing. Similarly, the disc file is opened with exclusive use because of the possibility of writing to it. There are no facilities in standard Fortran to control the locking and unlocking of records of a disc file as would be needed when adding a new record and updating the record count. This would be needed if separate tasks could be accessing the bit file at the same time, and is prevented by exclusive use. If an interactive system were prepared to respond to requests for ISPRIME(n), etc. it should open the bit file only for its query then close it before waiting for the next request - which might be many milliseconds away.
MODULE PRIMEBAG !Need prime numbers? Plenty are available.Although the structuralist talk up the merit of structured" constructs in programming, there are often annoying obstacles. With a WHILE-loop one usually has to repeat the "next item" code to "prime" the loop, as in
C Creates and expands a disc file for a sieve of Eratoshenes, representing odd numbers only and starting with three.
C Storage requirements: an array of N prime numbers in 16/32/64 bits vs. a bit array up to the 16/32/64 bit limit.
C Word size N Prime N words in bits Bit array in bits.
C 8 bit P(31) = 127 248 128
C P(54) = 251 432 256
C 16 bit P(3,512) = 32,749 56,192 32,768
C P(6,542) = 65,521 104,672 65,536
C 32 bit P(105,097,565) = 2,147,483,647 3,363,122,080 2,147,483,648
C P(203,280,221) = 4,294,967,291 6,504,967,072 4,294,967,296
C 64 bit 2.112E17 ? 1.352E19 9,223,372,036,854,775,808 ~ 9.22E18
C from n/Ln(n) 4.158E17 ? 2.661E19 18,446,744,073,709,551,616 ~ 1.84E19
INTEGER MSG !I/O unit number.
INTEGER SSTASH !For attachment to my stash file.
INTEGER SRECLEN,SCHARS,SBITS !Sizes.
INTEGER SORG !Where the sieve starts. This must be three.
INTEGER SLAST !Last record in my stash file.
DATA SSTASH,SREC,SLAST/0,0,0/ !Prepared by PRIMEBAG.
PARAMETER (SRECLEN = 1024) !4K disc bloc size, but RECL (in OPEN) is in terms of four-byte integers.
PARAMETER (SCHARS = (SRECLEN - 1)*4) !Reserving space for one number at the start.
PARAMETER (SBITS = SCHARS*8) !Known size of a character.
PARAMETER (SORG = 3) !First odd number past two, which is not odd.
CHARACTER*(*) SFILE !A name is needed.
PARAMETER (SFILE = "C:/Nicky/RosettaCode/Primes/PrimeSieve.bit") !I don't have to count the characters.
Components of a buffered record for the stash.
INTEGER SREC !The record number.
CHARACTER*1 C4(4) !The start of the record - a counter.
CHARACTER*1 SCHAR(0:SCHARS - 1) !The majority of the record - a bit array, packed in 8-bit blobs...
Collect some bit twiddling assistants for AND and OR, rather than bit shifting.
CHARACTER*1 BITON(0:7),BITOFF(0:7) !Functions IBSET and IBCLR may not be available, and are little-endian anyway.
PARAMETER (BITON =(/CHAR(2#10000000),CHAR(2#01000000), !128, 64, Reading strictly left-to-right.
1 CHAR(2#00100000),CHAR(2#00010000), ! 32, 16, Uncompromising bigendery.
1 CHAR(2#00001000),CHAR(2#00000100), ! 8, 4, Not just for bytes in words,
3 CHAR(2#00000010),CHAR(2#00000001)/)) ! 2, 1. But also bits in bytes.
PARAMETER (BITOFF=(/CHAR(2#01111111),CHAR(2#10111111), !127, 191, BITON + BITOFF = 255.
2 CHAR(2#11011111),CHAR(2#11101111), !223, 239,
1 CHAR(2#11110111),CHAR(2#11111011), !247, 251,
3 CHAR(2#11111101),CHAR(2#11111110)/)) !253, 254.
CONTAINS
INTEGER FUNCTION I4UNPACK(C4) !Convert four successive characters into an integer.
CHARACTER*1 C4(4) !The characters.
I4UNPACK = ((ICHAR(C4(1))*256 + ICHAR(C4(2)))*256 !Convert the first four bytes
1 + ICHAR(C4(3)))*256 + ICHAR(C4(4)) !To a four-byte integer.
END FUNCTION I4UNPACK !Big-endian style, irrespective of cpu endianness.
SUBROUTINE C4PACK(I4) !Convert an integer into successive bytes.
Could return the result via a fancy function, but for now a global variable will do.
INTEGER I4,N !The integer, and a copy to damage.
INTEGER I !A stepper.
N = I4 !Keep the original safe.
DO I = 4,1,-1 !Know that four characters will do. Fixed format makes this easy.
C4(I) = CHAR(MOD(N,256)) !Grab the low-order eight bits.
N = N/256 !And shift right eight.
END DO !Do it again.
END SUBROUTINE C4PACK !Stored big-endianly, irrespective of cpu endianness.
LOGICAL FUNCTION GRASPPRIMEBAG(F)
INTEGER F !The I/O unit number to use.
LOGICAL EXIST !Use the keyword as a name
INTEGER IOSTAT !And don't worry over assignment direction.
CHARACTER*3 STYLE !One way or another.
SSTASH = F !I shall use it.
INQUIRE (FILE = SFILE,EXIST = EXIST) !Trouble with a missing "path" may arise.
IF (EXIST) THEN !If the file exists,
STYLE = "OLD" !I shall read it.
ELSE !But if it doesn't,
STYLE = "NEW" !I shall create it.
END IF !Enough prevarication.
OPEN(SSTASH,FILE = SFILE, STATUS = STYLE, !Go for the file.
& ACCESS = "DIRECT", RECL = SRECLEN, FORM = "UNFORMATTED", !I have plans.
& ERR = 666, IOSTAT = IOSTAT) !Which may be thwarted.
IF (EXIST) THEN !If there is one...
CALL READSCHAR(1) !The first record is also a header.
SLAST = I4UNPACK(C4) !The number of records stored.
ELSE !Otherwise, start from scratch.
SLAST = 0 !No saved records.
CALL PSURGE(SCHAR) !During preparation of the first batch of bits.
END IF !All should now be in readiness.
GRASPPRIMEBAG = .TRUE.!So, feel confidence.
RETURN !And escape.
666 WRITE (*,667) IOSTAT,SFILE !But, something may have gone wrong.
667 FORMAT ("Pox! Error code ",I0, !A "hole" in the directory path?
1 " when attempting to open file ",A) !Read-only access allowed when I want "update"?
GRASPPRIMEBAG = .FALSE. !Whatever, it didn't work.
END FUNCTION GRASPPRIMEBAG !So much for that.
SUBROUTINE READSCHAR(R) !Get record R into SCHAR, which may already hold it.
INTEGER R !The record number desired.
IF (R.EQ.SREC) RETURN !Perhaps it is already to hand.
SREC = R !If not, move attention to it.
READ (SSTASH,REC = SREC) C4,SCHAR !And read the record.
END SUBROUTINE READSCHAR!Thus, I have a buffer too.
LOGICAL FUNCTION PSURGE(BIT8) !Add another record to the stash.
C Surges forward into the next batch of primes, to be stored via a bit array in the file.
C Each record starts with a count of the number of primes that have gone before.
C Except that for the first record, this is the record counter for the stash file.
C Except that when starting the second record, one is also the number of primes before SORG.
CHARACTER*1 BIT8(0:SCHARS - 1) !Watch out! This may be SCHAR itself!
INTEGER IST,LST !The numbers spanned by the surge.
INTEGER F !A factor.
INTEGER I !Another factor and a stepper.
INTEGER C !Index for array BIT8.
INTEGER NP !Number of primes.
Carry forward the count of previous primes to start the following record..
10 IF (SLAST.GT.0) THEN !Is there a previous record?
CALL READSCHAR(SLAST) !Yes. Grab it. A good chance this is already in C4,SCHAR.
NP = I4UNPACK(C4) !Its count of the primes accumulated before it.
DO I = 0,SCHARS - 1 !Find out how namy primes it fingered by scanning its bits.
NP = NP + COUNT(IAND(ICHAR(SCHAR(I)),ICHAR(BITON)).NE.0) !Whee! Eight at a go!
END DO !On to the next byte.
END IF !When creating a new record, its follower may not be sought in this run.
Concoct the next batch of bits. Contorted calculations avoid integer overflow.
20 BIT8 = CHAR(255) !All bits are aligned with numbers that might prove to be prime.
IST = SORG + SLAST*(2*SBITS) !Bit(0) of BIT8(0) corresponds to IST.
LST = IST + 2*(SBITS - 1) !Bit(last) to this number. Remember, only odd numbers have bits.
IF (IST.LE.0) THEN !Humm. I'd better check.
WRITE (MSG,21) SLAST,IST,LST !This works only with two's complement integers.
21 FORMAT (/,"Integer overflow in the sieve of Eratosthenes!", !Oh dear.
1 /,"Advancing from surge ",I0," to span ",I0," to ",I0) !These numbers will look odd.
PSURGE = .FALSE. !But it is better than no indication of what went wrong.
RETURN !Give in.
END IF !Enough worrying.
F = 3 !The first possible factor. Zapping will start at F²
c DO WHILE(F.LE.LST/F) !If F² is past the end, so will be still larger F: enough.
DO WHILE(F.LE.IST/F + (MOD(IST,F) + 2*(SBITS - 1))/F) !"Synthetic division" avoiding overflow.
I = (IST - 1)/F + 1 !I want the first multiple of F in IST:LST. F may be a factor of IST.
IF (MOD(I,2).EQ.0) I = I + 1!If even, advance to the next odd multiple. Even numbers are omitted by design.
IF (I.LT.F) I = F !Less than F is superfluous: the position was zapped by earlier action.
c I = (I*F - IST)/2 !Current bit positions are for IST, IST+2, IST+4, etc.
I = ((I - IST/F)*F - MOD(IST,F))/2 !Avoids overflow when calculating the start value, I*F.
DO I = I,SBITS - 1,F !Zap every F'th bit along. This is the sieve of Eratosthenes.
C = I/8 !Eight bits per character.
BIT8(C) = CHAR(IAND(ICHAR(BIT8(C)), !For F = 3 and 5, characters will be hit more than once.
1 ICHAR(BITOFF(MOD(I,8))))) !Whack a bit. All the above just for this!
END DO !On to the next bit.
22 F = NEXTPRIME(F) !So much for F. Next, please.
END DO !Are we there yet?
Correct the count in the header, if this is an added record.
30 IF (SLAST.GT.0) THEN !So, was there a pre-existing header record?
CALL READSCHAR(1) !Yes. Get the header record into C4,SCHAR.
CALL C4PACK(SLAST + 1) !This is the new record count.
WRITE (SSTASH,REC = 1) C4,SCHAR !Write it all back.
SCHAR = BIT8 !Ensure that SCHAR and SREC will be agreed.
END IF !So much for the header's count.
Cast the bits into the stash by writing record SLAST + 1..
40 IF (SLAST.EQ.0) THEN !If we're writing the first record,
CALL C4PACK(1) !Then this is the record count.
ELSE !Otherwise,
CALL C4PACK(NP) !Place the previous primes count.
END IF !All this to help PRIME(i).
SLAST = SLAST + 1 !This is now the last stashed record.
WRITE (SSTASH,REC = SLAST) C4,BIT8 !I/O directly from the work area?
SREC = SLAST !This is where BIT8 was written.
PSURGE = .TRUE. !That assumes BIT8 is not SCHAR for SLAST > 1.
END FUNCTION PSURGE !That was fun!
RECURSIVE SUBROUTINE GETSREC(R) !Make present the bit array belonging to record R.
INTEGER R !The record number..
CHARACTER*1 BIT8(0:SCHARS - 1) !A scratchpad. Others may be relying on SCHAR.
IF (SLAST.LE.0) RETURN!DANGER! The first record is being initialised!
DO WHILE(SLAST.LT.R) !If we haven't reached so far,
IF (.NOT.PSURGE(BIT8)) THEN !Slog forwards one record's worth.
WRITE (MSG,1) R !Or maybe not.
1 FORMAT ("Cannot prepare surge ",I0) !Explain.
STOP "No bits, no go." !And quit.
END IF !And having prepared the next block of bits,
END DO !Check afresh.
CALL READSCHAR(R) !Read the desired record's bits.
END SUBROUTINE GETSREC !Done.
INTEGER FUNCTION PRIME(N) !P(1) = 2, P(2) = 3, etc.
C Calculate P(n) ~ n.ln(n)
C ~ n{ln(n) + ln(ln(n)) - 1 + (ln(ln(n)) - 2)/ln(n) - [ln(ln(n))**2 - 6*log(log(n)) + 11]/[2*(ln(n))**2] + ....}
C J.B.Rosser's 1938 Theorem: n[ln(n) + ln(ln(n)) - 1] < P(n) < n[ln(n) + ln(ln(n))]
C or, with E = ln(n) + ln(ln(n)), n[E - 1] < P(n) < n[E]
C Experimentation shows that the undershoot of the first two terms involves many records worth of bits.
C Including additional terms does much better, but can overshoot.
INTEGER N !The desired one.
INTEGER R,NP !Counts.
INTEGER B,C !Bit and character indices.
DOUBLE PRECISION EST,LN,LLN !Hope, if not actuality.
IF (N.LE.0) STOP "Primes are counted positively!" !Something must be wrong!
IF (N.LE.1) THEN !The start of the bit array being preempted.
PRIME = 2 !So, no array access.
ELSE !Otherwise, the fun begins.
LN = LOG(DFLOAT(N)) !Here we go.
LLN = LOG(LN) !A popular term.
EST = N*(LN !Estimate the value of the N'th prime.
1 + LLN - 1 !Second term
2 + (LLN - 2)/LN !Third term.
3 - (LLN**2 - 6*LLN + 11)/(2*LN**2)) !Fourth term.
R = (EST - SORG)/(2*SBITS) + 1 !Thereby selecting a record to scan.
IF (R.LE.0) R = 1 !And not making a mess with N < 6 or so.
9 CALL GETSREC(R) !Go for the record.
IF (R.LE.1) THEN !The first record starts with the record count.
NP = 1 !And I know how many primes precede its start point
ELSE !While for all subsequent records,
NP = I4UNPACK(C4) !This counts the number of primes that precede record R's start number.
END IF !So now I'm ready to count onwards.
IF (N.LE.NP) THEN !Maybe not.
R = R - 1 !The estimate took me too far ahead.
GO TO 9 !Try again.
END IF !Could escalate to a binary search or even an interpolating search.
Commence scanning the bits.
C = 0 !Start with the first character of SREC..
B = -1 !Syncopation. The formula is known to always under-estimate.
10 IF (NP.LT.N) THEN !Are we there yet?
11 B = B + 1 !No. Advance to the next bit.
IF (B.GE.8) THEN !Overflowed a character yet?
B = 0 !Yes. Start afresh at the first bit.
C = C + 1 !And advance one character.
IF (C.GE.SCHARS) THEN !Overflowed the record yet?
C = 0 !Yes. Start afresh at its first character.
R = R + 1 !And advance to the next record.
CALL GETSREC(R) !Possibly, create it.
END IF !So much for records.
END IF !We're now ready to test bit B of character C of record R.
IF (IAND(ICHAR(SCHAR(C)),ICHAR(BITON(B))).EQ.0) GO TO 11 !Not a prime. Search on.
NP = NP + 1 !Count another prime.
GO TO 10 !Pehaps this will be the one.
END IF !So much for the search.
PRIME = SORG + (R - 1)*(2*SBITS) + (C*8 + B)*2 !The corresponding number.
IF (PRIME.LE.0) WRITE (MSG,666) N,PRIME !Or, possibly not.
666 FORMAT ("Integer overflow! Prime(",I0,") gives ",I0,"!") !Let us hope the caller notices.
END IF !So, all going well,
END FUNCTION PRIME !It is found.
RECURSIVE INTEGER FUNCTION NEXTPRIME(N) !Keep right on to the end of the road.
Can invoke GETSREC, which can invoke PSURGE, which ... invokes NEXTPRIME. Oh dear.
INTEGER N !Not necessarily itself a prime number.
INTEGER NN !A value to work with.
INTEGER R !A record number into the stash.
INTEGER I,IST !Number offsets.
INTEGER C,B !Character and bit index.
IF (N.LE.1) THEN !Suspicion prevails.
NN = 2 !This is not represented in my bit array.
ELSE !Otherwise, the fun begins.
NN = N + 1 !Advance, with a copy I can mess with.
IF (MOD(NN,2).EQ.0) NN = NN + 1 !Thus, NN is now odd.
IF (NN.LE.0) GO TO 666 !But perhaps not proper, due to overflow.
R = (NN - SORG)/(2*SBITS) !SORG is odd, so (NN - SORG) is even.
CALL GETSREC(R + 1) !The first record is numbered one, not zero.
IST = SORG + R*(2*SBITS) !The number for its first bit: even numbers are omitted..
I = (NN - IST)/2 !Offset into the record. NN - IST is even.
C = I/8 !Which character in SCHAR(0:SCHARS - 1)?
B = MOD(I,8) !Which bit in SCHAR(C)?
10 IF (IAND(ICHAR(SCHAR(C)),ICHAR(BITON(B))).EQ.0) THEN !On for a prime.
NN = NN + 2 !Alas, it is off, so NN is not a prime. Perhaps this will be.
B = B + 1 !Advance one bit. Each bit steps two.
IF (B.GE.8) THEN !Past the end of the character?
B = 0 !Yes. Back to bit zero.
C = C + 1 !And advance one chracter.
IF (C.GE.SCHARS) THEN !Past the end of the record?
IF (NN.LE.0) GO TO 666!Yes. If NN has overflowed, the end of the rope is reached.
C = 0 !Back to the start of a record.
R = R + 1 !Advance one record.
CALL GETSREC(R + 1) !And read it. (Count is from 1, not 0).
END IF !So much for overflowing a record.
END IF !So much for overflowing a character.
GO TO 10 !Try again.
END IF !So much for the bit array.
END IF !If there had been a scan.
NEXTPRIME = NN !The number for which the scan stopped.
IF (NN.GT.0) RETURN !All is well.
666 WRITE (MSG,667) N,NN !Or, maybe not. Careful: this won't appear if NEXTPRIME is invoked in a WRITE list.
667 FORMAT ("Integer overflow! NextPrime(",I0,") gives ",I0,"!") !The recipient could do a two's complement.
NEXTPRIME = NN !Prefer to return the bad value rather than fail to return anything.
END FUNCTION NEXTPRIME !No divisions, no sieving. Here, anyway
INTEGER FUNCTION PREVIOUSPRIME(N) !If N is good, this can't overflow.
INTEGER N !The number, not necessarily a prime.
INTEGER NN !A value to mess with.
INTEGER R !A record number.
INTEGER I !Offset.
INTEGER C,B !Character and bit fingers.
IF (N.LE.3) THEN !Suppress annoyances.
NN = 2 !This is now called the first prime, not one.
ELSE !Otherwise, some work is to be done.
NN = N - 1 !Step back one to ensure previousness.
IF (MOD(NN,2).EQ.0) NN = NN - 1 !And here, oddness is a minimal requirement.
R = (NN - SORG)/(2*SBITS) !Finger the record containing the bit for NN.
CALL GETSREC(R + 1) !Record counting starts with one.
I = (NN - (SORG + R*(2*SBITS)))/2 !Offset into that record.
C = I/8 !Finger the character in SCHAR.
B = MOD(I,8) !And the bit within the character.
10 IF (IAND(ICHAR(SCHAR(C)),ICHAR(BITON(B))).EQ.0) THEN !On for a prime.
NN = NN - 2 !Alas, it is off, so NN is not a prime. Perhaps this will be.
B = B - 1 !Retreat one bit. Each bit steps two.
IF (B.LT.0) THEN !Past the start of the character?
B = 7 !Yes. Back to the last bit.
C = C - 1 !And retreat one chracter.
IF (C.LT.0) THEN !Past the start of the record?
C = SCHARS - 1 !Yes. Back to the end of a record.
R = R - 1 !Retreat one record.
CALL GETSREC(R + 1) !And read it. (Count is from 1, not 0).
END IF !So much for overflowing a record.
END IF !So much for overflowing a character.
GO TO 10 !Try again.
END IF !So much for the bit array.
END IF !Possibly, it was not needed.
PREVIOUSPRIME = NN !There.
END FUNCTION PREVIOUSPRIME !Doesn't overflow, either.
LOGICAL FUNCTION ISPRIME(N) !Could fool around explicity testing 2 and 3 and say 5,
INTEGER N !But that means also checking that N > 2, N > 3, and N > 5.
ISPRIME = N .EQ. NEXTPRIME(N - 1) !This is so much easier.
END FUNCTION ISPRIME !No divisions up to SQRT(N) or the like either.
END MODULE PRIMEBAG !Functions updating a disc file as a side effect...
PROGRAM POKE
USE PRIMEBAG
INTEGER I,P,N,N1,N2 !Assorted assistants.
INTEGER ORDER !A collection of special values.
PARAMETER (ORDER = 6) !For one, two, and four byte integers.
INTEGER EDGE(ORDER) !Considered as two's complement and unsigned.
PARAMETER (EDGE = (/31,54,3512,6542,105097565,203280221/)) !These primes are of interest.
MSG = 6 !Standard output.
IF (.NOT.GRASPPRIMEBAG(66)) STOP "Gan't grab my file!" !Attempt in hope.
Case 1.
C FORALL(I = 1:20) LIST(I) = PRIME(I) is rejected because function Prime(i) is rather impure.
10 WRITE (MSG,11)
11 FORMAT (19X,"First twenty primes: ", $)
DO I = 1,20
P = PRIME(I)
WRITE (MSG,12) P
12 FORMAT (I0,",",$)
END DO
Case 2.
20 WRITE (MSG,21)
21 FORMAT (/,12X,"Primes between 100 and 150: ",$)
P = 100
22 P = NEXTPRIME(P) !While (P:=NextPrime(P)) <= 150 do Print P;
IF (P.LE.150) THEN !But alas, no assignment within an expression.
WRITE (MSG,23) P
23 FORMAT (I0,",",$)
GO TO 22
END IF
Case 3.
30 N1 = 7700 !Might as well parameterise this.
N2 = 8000 !Rather than litter the source with explicit integers.
N = 0
P = N1
31 P = NEXTPRIME(P)
IF (P.LE.N2) THEN
N = N + 1
GO TO 31
END IF
WRITE (MSG,32) N1,N2,N
32 FORMAT (/"Number of primes between ",I0," and ",I0,": ",I0)
Case 4.
40 WRITE (MSG,41)
41 FORMAT (/,"Tenfold steps...")
N = 1
DO I = 1,9 !This goes about as far as it can go.
P = PRIME(N)
WRITE (MSG,42) N,P
42 FORMAT ("Prime(",I0,") = ",I0)
N = N*10
END DO
Cast forth some interesting values.
100 WRITE (MSG,101)
101 FORMAT (/,"Primes close to number sizes")
DO N = 1,ORDER !Step through the list.
N1 = EDGE(N) - 1 !Syncopation for the special value.
DO I = 1,2 !I want the prime on either side.
N1 = N1 + 1 !So, there are two successive primes to finger.
WRITE (MSG,102) N1 !Identify the index.
102 FORMAT ("Prime(",I0,") = ",$) !Piecemeal writing to the output,
P = PRIME(N1) !As this may fling forth a complaint.
WRITE (MSG,103) P !Show the value returned.
103 FORMAT (I0,", ",$) !Which may be unexpected.
END DO !On to the second.
WRITE (MSG,*) !End the line after the second result.
END DO !On to the next in the list.
END !Whee!
P = NEXTPRIME(100)While this is not a large imposition in this example, if Fortran were to allow assignment within expressions as in Algol, the tedium of code replication and its risks could be avoided.
DO WHILE (P.LE.150)
...stuff...
P = NEXTPRIME(P)
END DO
P:=100; WHILE (P:=NextPrime(P)) <= 150 DO stuff;If instead of NEXTPRIME the "next item" code was to read a record of a disc file, the repetition needed becomes tiresome. So, an IF-statement, and ... a GO TO...
The Results[edit]
When creating the bit file, everything appears in a blink up to the millionth prime, then a pause until the ten millionth prime, then about a minute to attain the hundred millionth prime. The blinking lights show that there is not much disc I/O in progress (actually, a solid-state unit) while the cpu is running at full speed. There is a further pause from there until overflow is reached. For a subsequent run with the disc file already prepared, all is completed in a blink. Pausing the Great Internet Mersenne Prime crunch (sixfold) increases the speed and I/O rate by about a third. During the file expansion, the rate of I/O slowly decreases at a decreasing rate - this is due to each successive sieve surge requiring more primes to step with, but the primes themselves thin out and being larger, require fewer steps to traverse the span. The effort for each surge is related to the sum of the reciprocals of the primes that will sieved with and this forms an interesting sequence in its own right. For a given surge width, fewer and fewer hits are made within that width by the larger prime numbers. However, 4092 bytes (four are reserved for the count, and on this windows XP system disc space is allocated in blocks of 4k) gives 32736 bits which with odd numbers only, spans 65472. With 32-bit two's complement, sqrt(2,147,483,647) = 46340·95 so even the largest stepper will land at least once within every span, except that only odd multiples are involved so already the hit rate has drifted below one per span and with extension to still larger numbers, the hit rate will fall further. Thus, if instead each pass were to be for the full width of the bit array in the disc file, the I/O system would suffer a thrashing during the multiple passes unless the entire file could be fitted into random-access memory. But such a scheme would not have the "extensible" aspect.
Output:
First twenty primes: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, Primes between 100 and 150: 101,103,107,109,113,127,131,137,139,149, Number of primes between 7700 and 8000: 30 Tenfold steps... Prime(1) = 2 Prime(10) = 29 Prime(100) = 541 Prime(1000) = 7919 Prime(10000) = 104729 Prime(100000) = 1299709 Prime(1000000) = 15485863 Prime(10000000) = 179424673 Prime(100000000) = 2038074743 Primes close to number sizes Prime(31) = 127, Prime(32) = 131, Prime(54) = 251, Prime(55) = 257, Prime(3512) = 32749, Prime(3513) = 32771, Prime(6542) = 65521, Prime(6543) = 65537, Prime(105097565) = 2147483647, Prime(105097566) = Integer overflow! Prime(105097566) gives -2147483637! -2147483637, Prime(203280221) = Integer overflow in the sieve of Eratosthenes! Advancing from surge 32801 to span -2147420221 to -2147354751 Cannot prepare surge 65601 No bits, no go.
The disc file holding all primes up to the thirty-two bit limit occupies 134,352,896 bytes, or 128MB. Nothing much, these days. Activating 7-zip out of curiosity resulted in compressing the file by a factor of two. As the primes thin out there will be more and more characters with only one bit on (if not none) rather than a fuller selection. However, the existence of prime pairs shows that the bits will never be all lonely forever. For this run, the last record is number 32,801 and 105,097,477 (hex 643A905) primes have gone before.
First value Bit array... 3: 11101101 10100110 01011010 01001100 10110010 10010001 01101101 00000010 10011000 01100100 10100100 11000011 01100000 10000010 11010011 00001001 00100110 01011000 01000000 10110100 00001001 00001101 00100010 01001010 01000101 00010000 11000011 00101001 00010110 10000010 00101000 10100100 ... 2147481603: 00000000 00000100 00000000 00000000 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 01000000 10000000 10000000 00000000 00100000 00001000 01001100 10000000 00000001 00000100 00000010 00000000 00000100 00000000 01000000 00000000 00000010 00000001 00001100 00000000 ...
Would anyone prefer to see that bit array in the little-endian order within bytes?
A more accomplished data compression system might instead offer a reference to a library containing a table of prime numbers, or even store the code for a programme that will generate the data. File Pbag.for is 23,008 bytes long, and of course contains irrelevant commentary and flabby phrases such as "PARAMETER", "INTEGER", "GRASPPRIMEBAG", etc. As is the modern style, the code file is much larger at 548,923 bytes (containing kilobyte sequences of hex CC and of 00), but both are much smaller than the 134,352,896 bytes of file PrimeSieve.bit.
FreeBASIC[edit]
This program uses the Sieve Of Eratosthenes which is not very efficient for large primes but is quick enough for present purposes.
The size of the sieve array (of type Boolean) is calculated as 20 times the number of primes required which is big enough to compute up to 50 million primes (a sieve size of 1 billion bytes) which takes under 50 seconds on my i3 @ 2.13 GHz. I've limited the procedure to this but it should certainly be possible to use a much higher figure without running out of memory.
It would also be possible to use a more efficient algorithm to compute the optimal sieve size for smaller numbers of primes but this will suffice for now.
' FB 1.05.0
Enum SieveLimitType
number
between
countBetween
End Enum
Sub printPrimes(low As Integer, high As Integer, slt As SieveLimitType)
If high < low OrElse low < 1 Then Return ' too small
If slt <> number AndAlso slt <> between AndAlso slt <> countBetween Then Return
If slt <> number AndAlso (low < 2 OrElse high < 2) Then Return
If slt <> number AndAlso high > 1000000000 Then Return ' too big
If slt = number AndAlso high > 50000000 Then Return ' too big
Dim As Integer n
If slt = number Then
n = 20 * high '' big enough to accomodate 50 million primes to which this procedure is limited
Else
n = high
End If
Dim a(2 To n) As Boolean '' only uses 1 byte per element
For i As Integer = 2 To n : a(i) = True : Next '' set all elements to True to start with
Dim As Integer p = 2, q
' mark non-prime numbers by setting the corresponding array element to False
Do
For j As Integer = p * p To n Step p
a(j) = False
Next j
' look for next True element in array after 'p'
q = 0
For j As Integer = p + 1 To Sqr(n)
If a(j) Then
q = j
Exit For
End If
Next j
If q = 0 Then Exit Do
p = q
Loop
Select Case As Const slt
Case number
Dim count As Integer = 0
For i As Integer = 2 To n
If a(i) Then
count += 1
If count >= low AndAlso count <= high Then
Print i; " ";
End If
If count = high Then Exit Select
End If
Next
Case between
For i As Integer = low To high
If a(i) Then
Print i; " ";
End if
Next
Case countBetween
Dim count As Integer = 0
For i As Integer = low To high
If a(i) Then count += 1
Next
Print count;
End Select
End Sub
Print "The first 20 primes are :"
printPrimes(1, 20, number)
Print "The primes between 100 and 150 are :"
printPrimes(100, 150, between)
Print "The number of primes between 7700 and 8000 is :";
printPrimes(7700, 8000, countBetween)
Print "The 10000th prime is :";
Dim t As Double = timer
printPrimes(10000, 10000, number)
Print "Computed in "; CInt((timer - t) * 1000 + 0.5); " ms"
Print "The 1000000th prime is :";
t = timer
printPrimes(1000000, 1000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print "The 50000000th prime is :";
t = timer
printPrimes(50000000, 50000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print "Press any key to quit"
Sleep
- Output:
The first 20 primes are : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 The primes between 100 and 150 are : 101 103 107 109 113 127 131 137 139 149 The number of primes between 7700 and 8000 is : 30 The 10000th prime is : 104729 Computed in 8 ms The 1000000th prime is : 15485863 Computed in 775 ms The 50000000th prime is : 982451653 Computed in 46703 ms
Go[edit]
An implementation of "The Genuine Sieve of Eratosthenese" by Melissa E. O'Niell. This is the paper cited above in the "Faster Alternative Version" of D. The Go example here though strips away optimizations such as a wheel to show the central idea of storing prime multiples in a queue data structure.
package main
import (
"container/heap"
"fmt"
)
func main() {
p := newP()
fmt.Print("First twenty: ")
for i := 0; i < 20; i++ {
fmt.Print(p(), " ")
}
fmt.Print("\nBetween 100 and 150: ")
n := p()
for n <= 100 {
n = p()
}
for ; n < 150; n = p() {
fmt.Print(n, " ")
}
for n <= 7700 {
n = p()
}
c := 0
for ; n < 8000; n = p() {
c++
}
fmt.Println("\nNumber beween 7,700 and 8,000:", c)
p = newP()
for i := 1; i < 10000; i++ {
p()
}
fmt.Println("10,000th prime:", p())
}
func newP() func() int {
n := 1
var pq pQueue
top := &pMult{2, 4, 0}
return func() int {
for {
n++
if n < top.pMult { // n is a new prime
heap.Push(&pq, &pMult{prime: n, pMult: n * n})
top = pq[0]
return n
}
// n was next on the queue, it's a composite
for top.pMult == n {
top.pMult += top.prime
heap.Fix(&pq, 0)
top = pq[0]
}
}
}
}
type pMult struct {
prime int
pMult int
index int
}
type pQueue []*pMult
func (q pQueue) Len() int { return len(q) }
func (q pQueue) Less(i, j int) bool { return q[i].pMult < q[j].pMult }
func (q pQueue) Swap(i, j int) {
q[i], q[j] = q[j], q[i]
q[i].index = i
q[j].index = j
}
func (p *pQueue) Push(x interface{}) {
q := *p
e := x.(*pMult)
e.index = len(q)
*p = append(q, e)
}
func (p *pQueue) Pop() interface{} {
q := *p
last := len(q) - 1
e := q[last]
*p = q[:last]
return e
}
- Output:
First twenty: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 Number beween 7,700 and 8,000: 30 10,000th prime: 104729
An alternative showing how to use a good and very fast open source Sieve of Atkin implementation
via github.com/jbarham/primegen.go.
Due to how Go's imports work, the bellow can be given directly to "go run
" or "go build
" and the latest version of the primegen package will be fetched and built if it's not already present on the system.
(This example may not be exactly within the scope of this task, but it's a trivial to use and extremely fast prime generator probably worth considering whenever primes are needed in Go.)
package main
import (
"fmt"
"github.com/jbarham/primegen.go"
)
func main() {
p := primegen.New()
fmt.Print("First twenty: ")
for i := 0; i < 20; i++ {
fmt.Print(p.Next(), " ")
}
fmt.Print("\nBetween 100 and 150: ")
p.SkipTo(100)
for n := p.Next(); n < 150; n = p.Next() {
fmt.Print(n, " ")
}
p.SkipTo(7700)
fmt.Println("\nNumber beween 7,700 and 8,000:", p.Count(8000))
p.Reset()
for i := 1; i < 1e4; i++ {
p.Next()
}
fmt.Println("10,000th prime:", p.Next())
}
Haskell[edit]
This program uses the primes package, which uses a lazy wheel sieve to produce an infinite list of primes.
#!/usr/bin/env runghc
import Data.List
import Data.Numbers.Primes
import System.IO
firstNPrimes :: Integer -> [Integer]
firstNPrimes n = genericTake n primes
primesBetweenInclusive :: Integer -> Integer -> [Integer]
primesBetweenInclusive lo hi =
dropWhile (< lo) $ takeWhile (<= hi) primes
nthPrime :: Integer -> Integer
nthPrime n = genericIndex primes (n - 1) -- beware 0-based indexing
main = do
hSetBuffering stdout NoBuffering
putStr "First 20 primes: "
print $ firstNPrimes 20
putStr "Primes between 100 and 150: "
print $ primesBetweenInclusive 100 150
putStr "Number of primes between 7700 and 8000: "
print $ genericLength $ primesBetweenInclusive 7700 8000
putStr "The 10000th prime: "
print $ nthPrime 10000
- Output:
First 20 primes: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71] Primes between 100 and 150: [101,103,107,109,113,127,131,137,139,149] Number of primes between 7700 and 8000: 30 The 10000th prime: 104729
List based[edit]
Using list based unbounded sieve from here (runs instantly):
λ> take 20 primesW
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
λ> takeWhile (< 150) . dropWhile (< 100) $ primesW
[101,103,107,109,113,127,131,137,139,149]
λ> length . takeWhile (< 8000) . dropWhile (< 7700) $ primesW
30
λ> (!! (10000-1)) primesW
104729
Icon and Unicon[edit]
Only works in Unicon (use of the Heap class). Brute force.
The expression:
![2,3,5,7] | (nc := 11) | (nc +:= |wheel2345)
is an open-ended sequence generating potential primes.
import Collections # to get the Heap class for use as a Priority Queue
record filter(composite, prime) # next composite involving this prime
procedure main()
every writes((primes()\20)||" " | "\n")
every p := primes() do if 100 < p < 150 then writes(p," ") else if p >= 150 then break write()
every (n := 0, p := primes()) do if 7700 < p < 8000 then n +:= 1 else if p >= 8000 then break write(n)
every (i := 1, p := primes()) do if (i+:=1) >= 10000 then break write(p)
end
procedure primes()
local wheel2357, nc
wheel2357 := [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6,
2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]
suspend sieve(Heap(,getCompositeField), ![2,3,5.7] | (nc := 11) | (nc +:= |!wheel2357))
end
procedure sieve(pQueue, candidate)
local nc
if 0 = pQueue.size() then { # 2 is prime
pQueue.add(filter(candidate*candidate, candidate))
return candidate
}
while candidate > (nc := pQueue.get()).composite do {
nc.composite +:= nc.prime
pQueue.add(nc)
}
pQueue.add(filter(nc.composite+nc.prime, nc.prime))
if candidate < nc.composite then { # new prime found!
pQueue.add(filter(candidate*candidate, candidate))
return candidate
}
end
# Provide a function for comparing filters in the priority queue...
procedure getCompositeField(x); return x.composite; end
- Output:
->ePrimes 2 3 5.7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 101 103 107 109 113 127 131 137 139 149 30 104729 ->
J[edit]
Using the p: builtin, http://www.jsoftware.com/help/dictionary/dpco.htm reports "Currently, arguments larger than 2^31 are tested to be prime according to a probabilistic algorithm (Miller-Rabin)".
p:i.20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
(#~ >:&100)i.&.(p:inv) 150
101 103 107 109 113 127 131 137 139 149
#(#~ >:&7700)i.&.(p:inv) 8000
30
p:10000-1
104729
Note: p: gives the nth prime, where 0 is first, 1 is second, 2 (cardinal) is third (ordinal) and so on...
Note: 4&p: gives the next prime
4 p: 104729
104743
JavaScript[edit]
primeGenerator(num, showPrimes) This function takes two arguments:
num is either an integer as a limit, or an array of two integers to present a range;
showPrimes is a boolean to indicate whether the result should be a list (if true) or a single number (if false).
Sounds a bit weird, but I hope it will be intelligible by the testing examples below. First the code:
function primeGenerator(num, showPrimes) {
var i,
arr = [];
function isPrime(num) {
// try primes <= 16
if (num <= 16) return (
num == 2 || num == 3 || num == 5 || num == 7 || num == 11 || num == 13
);
// cull multiples of 2, 3, 5 or 7
if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0)
return false;
// cull square numbers ending in 1, 3, 7 or 9
for (var i = 10; i * i <= num; i += 10) {
if (num % (i + 1) == 0) return false;
if (num % (i + 3) == 0) return false;
if (num % (i + 7) == 0) return false;
if (num % (i + 9) == 0) return false;
}
return true;
}
if (typeof num == "number") {
for (i = 0; arr.length < num; i++) if (isPrime(i)) arr.push(i);
// first x primes
if (showPrimes) return arr;
// xth prime
else return arr.pop();
}
if (Array.isArray(num)) {
for (i = num[0]; i <= num[1]; i++) if (isPrime(i)) arr.push(i);
// primes between x .. y
if (showPrimes) return arr;
// number of primes between x .. y
else return arr.length;
}
// throw a default error if nothing returned yet
// (surrogate for a quite long and detailed try-catch-block anywhere before)
throw("Invalid arguments for primeGenerator()");
}
Test
// first 20 primes
console.log(primeGenerator(20, true));
// primes between 100 and 150
console.log(primeGenerator([100, 150], true));
// numbers of primes between 7700 and 8000
console.log(primeGenerator([7700, 8000], false));
// the 10,000th prime
console.log(primeGenerator(10000, false));
Output
Array [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 59, 61, 67, 71 ]
Array [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 ]
30
104729
jq[edit]
Recent versions of jq include extensive support for unbounded stream generators, but in this section, we present a solution to the tasks that should work with any version of jq from 1.4 onwards. That is, instead of using an unbounded generator of a stream of primes, the core of the approach adopted here is a function, "extend_primes", which can be applied recursively to generate arbitrarily many, or indefinitely many, primes, as illustrated by the function named "primes" below.
Preliminaries:
# Recent versions of jq include the following definition:
# until/2 loops until cond is satisfied,
# and emits the value satisfying the condition:
def until(cond; next):
def _until:
if cond then . else (next|_until) end;
_until;
def count(cond): reduce .[] as $x (0; if $x|cond then .+1 else . end);
Prime numbers:
# Is the input integer a prime?
# "previous" must be the array of sorted primes greater than 1 up to (.|sqrt)
def is_prime(previous):
. as $in
| (previous|length) as $plength
| [false, 0] # state: [found, ix]
| until( .[0] or .[1] >= $plength;
[ ($in % previous[.[1]]) == 0, .[1] + 1] )
| .[0] | not ;
# extend_primes expects its input to be an array consisting of
# previously found primes, in order, and extends that array:
def extend_primes:
if . == null or length == 0 then [2]
else . as $previous
| if . == [2] then [2,3]
else . + [(2 + .[length-1]) | until( is_prime($previous) ; . + 2)]
end
end;
# If . is an integer > 0 then produce an array of . primes;
# otherwise emit an unbounded stream of primes:
def primes:
. as $n
| if type == "number" and $n > 0 then
null | until( length == $n; extend_primes )
else [2] | recurse(extend_primes) | .[length - 1]
end;
# Primes up to and possibly including n:
def primes_upto(n):
until( .[length-1] > n; extend_primes )
| if .[length-1] > n then .[0:length-1] else . end;
The tasks: The tasks are completed separately here to highlight the fact that by using "extend_primes", each task can be readily completed without generating unnecessarily many primes.
"First 20 primes:", (20 | primes), "",
"Primes between 100 and 150:",
(primes_upto(150) | map(select( 100 < .))), "",
"The 10,000th prime is \( 10000 | primes | .[length - 1] )", "",
(( primes_upto(8000) | count( . > 7700) | length) as $length
| "There are \($length) primes twixt 7700 and 8000.")
- Output:
$ jq -r -c -n -f Extensible_prime_generator.jq
First 20 primes:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
Primes between 100 and 150:
[101,103,107,109,113,127,131,137,139,149]
The 10,000th prime is 104729
There are 30 primes twixt 7700 and 8000.
Kotlin[edit]
Although we could use the java.math.BigInteger type to generate arbitrarily large primes, there is no need to do so here as the primes to be generated are well within the limits of the 4-byte Int type.
// version 1.1.1
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
import kotlin.coroutines.experimental.*
fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun generatePrimes() =
buildSequence {
yield(2)
var p = 3
while (p <= Int.MAX_VALUE) {
if (isPrime(p)) yield(p)
p += 2
}
}
fun main(args: Array<String>) {
val primes = generatePrimes().take(10000) // generate first 10,000 primes
println("First 20 primes : ${primes.take(20).toList()}")
println("Primes between 100 and 150 : ${primes.filter { it in 100..150 }.toList()}")
println("Number of primes between 7700 and 8000 = ${primes.filter { it in 7700..8000 }.count()}")
println("10,000th prime = ${primes.last()}")
}
- Output:
First 20 primes : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] Primes between 100 and 150 : [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] Number of primes between 7700 and 8000 = 30 10,000th prime = 104729
Mathematica / Wolfram Language[edit]
Prime and PrimePi use sparse caching and sieving. For large values, the Lagarias–Miller–Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime. PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
Prime[Range[20]]
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71}
Select[Range[100,150], PrimeQ]
{101, 103, 107, 109, 113, 127, 131, 137, 139, 149}
PrimePi[8000] - PrimePi[7700]
30
Prime[10000]
104729
PARI/GP[edit]
PARI includes a nice prime generator which is quite extensible:
void
showprimes(GEN lower, GEN upper)
{
forprime_t T;
if (!forprime_init(&T, a,b)) return;
while(forprime_next(&T))
{
pari_printf("%Ps\n", T.pp);
}
}
Most of these functions are already built into GP:
primes(20)
primes([100,150])
#primes([7700,8000]) /* or */
s=0; forprime(p=7700,8000,s++); s
prime(10000)
Pascal[edit]
The main intention is the use in http://rosettacode.org/wiki/Emirp_primes. The speed is about 3x times slower than sieve of Atkin.About 13 secs for 10 billion/146 secs for 100 billion in 64-Bit. But i can hold all primes til 1e11 in 2.5 Gb memory.Test for isEmirp inserted. 32-bit is slow doing 64-Bit math.Using a dynamic array is slow too in NextPrime.
program prime;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,REGVAR,PEEPHOLE,CSE,ASMCSE}
{$CODEALIGN proc=8}
// {$R+,V+,O+}
{$ELSE}
{$APPLICATION CONSOLE}
{$ENDIF}
uses
sysutils;
type
tSievenum = NativeUint;
const
cBitSize = SizeOf(tSievenum)*8;
cAndMask = cBitSize-1;
InitPrim :array [0..9] of byte = (2,3,5,7,11,13,17,19,23,29);
(*
{MAXANZAHL = 2*3*5*7*11*13*17*19;*PRIM}
MAXANZAHL :array [0..8] of Longint =(2,6,30,210,2310,30030,
510510,9699690,223092870);
{WIFEMAXLAENGE = 1*2*4*6*10*12*16*18; *(PRIM-1)}
WIFEMAXLAENGE :array [0..8] of longint =(1,2,8,48,480,5760,
92160,1658880,36495360);
*)
//Don't sieve with primes that are multiples of 2..InitPrim[BIS]
BIS = 5;
MaxMulFac = 22; {array [0..9] of byte= (2,4,6,10,14,22,26,34,40,50);}
cMaxZahl = 30030;
cRepFldLen = 5760;
MaxUpperLimit = 100*1000*1000*1000-1;
MAXIMUM = ((MaxUpperLimit-1) DIV cMaxZahl+1)*cMaxZahl;
MAXSUCHE = (((MAXIMUM-1) div cMaxZahl+1)*cRepFldLen-1)
DIV cBitSize;
type
tRpFldIdx = 0..cRepFldLen-1;
pNativeUint = ^ NativeUint;
(* numberField as Bit array *)
tsearchFld = array of tSievenum;
tSegment = record
dOfs,
dSegment :tSievenum;
end;
tpSegment = ^tSegment;
tMulFeld = array [0..MaxMulFac shr 1 -1] of tSegment;
tnumberField= array [0..cMaxZahl-1] of word; //word-> 0..cRepFldLen-1
tRevIdx = array [tRpFldIdx] of word;//word-> 0..cMaxZahl-1
tDiffFeld = array [tRpFldIdx] of byte;
tNewPosFeld = array [tRpFldIdx] of Uint64;
tRecPrime = record
rpPrime,
rpsvPos : Uint64;
rpOfs,
rpSeg :LongWord;
end;
var
BitSet,
BitClr : Array [0..cAndMask] Of NativeUint;
deltaNewPos : tNewPosFeld;
MulFeld : tMulFeld;
searchFld : tsearchFld;
number : tnumberField;
DiffFld : tDiffFeld;
RevIdx : tRevIdx;
actSquare : Uint64;
NewStartPos,
MaxPos : Uint64;
const
//K1 = $0101010101010101;
K55 = $5555555555555555;
K33 = $3333333333333333;
KF1 = $0F0F0F0F0F0F0F0F;
KF2 = $00FF00FF00FF00FF;
KF4 = $0000FFFF0000FFFF;
KF8 = $00000000FFFFFFFF;
function popcnt(n:Uint64):integer;overload;inline;
var
c,b,k : NativeUint;
begin
b := n;
k := NativeUint(K55);c := (b shr 1) AND k; b := (b AND k)+C;
k := NativeUint(K33);c := ((b shr 2) AND k);b := (b AND k)+C;
k := NativeUint(KF1);c := ((b shr 4) AND k);b := (b AND k)+c;
k := NativeUint(KF2);c := ((b shr 8) AND k);b := (b AND k)+c;
k := NativeUint(KF4);c := ((b shr 16) AND k);b := (b AND k)+c;
k := NativeUint(KF8);c := (b shr 32)+(b AND k);
result := c;
end;
function popcnt(n:LongWord):integer;overload;
var
c,k : LongWord;
begin
result := n;
IF result = 0 then
EXIT;
k := LongWord(K55);c := (result shr 1) AND k; result := (result AND k)+C;
k := LongWord(K33);c := ((result shr 2) AND k);result := (result AND k)+C;
k := LongWord(KF1);c := ((result shr 4) AND k);result := (result AND k)+c;
k := LongWord(KF2);c := ((result shr 8) AND k);result := (result AND k)+c;
k := LongWord(KF4);
result := (result shr 16) AND k +(result AND k);
end;
procedure Init;
{simple sieve of erathosthenes only eliminating small primes}
var
pr,i,j,Ofs : NativeUint;
Begin
//Init Bitmasks
j := 1;
For i := 0 to cAndMask do
Begin
BitSet[i] := J;
BitClr[i] := NativeUint(NOT(J));
j:= j+j;
end;
//building number wheel excluding multiples of small primes
Fillchar(number,SizeOf(number),#0);
For i := 0 to BIS do
Begin
pr := InitPrim[i];
j := (High(number) div pr)*pr;
repeat
number[j] := 1;
dec(j,pr);
until j <= 0;
end;
// build reverse Index and save distances
i := 1;
j := 0;
RevIdx[0]:= 1;
repeat
Ofs :=0;
repeat
inc(i);
inc(ofs);
until number[i] = 0;
DiffFld[j] := ofs;
inc(j);
RevIdx[j] := i;
until i = High(number);
DiffFld[j] := 2;
//calculate a bitnumber-index into cRepFldLen
Fillchar(number,SizeOf(number),#0);
Ofs := 1;
for i := 0 to cRepFldLen-2 do
begin
inc(Ofs,DiffFld[i]);
number[ofs] := i+1;
end;
//direct index into Mulfeld 2->0 ,4-> 1 ...
For i := 0 to cRepFldLen-1 do
Begin
j := (DiffFld[i] shr 1) -1;
DiffFld[i] := j;
end;
end;
function CalcPos(m: Uint64): Uint64;
{search right position of m}
var
i,res : NativeUint;
Begin
res := m div cMaxZahl;
i := m-res* Uint64(cMaxzahl);//m mod cMaxZahl
while (number[i]= 0) and (i <>1) do
begin
iF i = 0 THEN
begin
Dec(res,cRepFldLen);
i := cMaxzahl;
end;
dec(i);
end; {while}
CalcPos := res *Uint64(cRepFldLen) +number[i];
end;
procedure CalcSqrOfs(out Segment,Ofs :Uint64);
Begin
Segment := actSquare div cMaxZahl;
Ofs := actSquare-Segment*cMaxZahl; //ofs Mod cMaxZahl
Segment := Segment*cRepFldLen;
end;
procedure MulTab(sievePr:Nativeint);
var
k,Segment,Segment0,Rest,Rest0: NativeUint;
Begin
{multiplication-table of differences}
{2* sievePr,4* ,6* ...MaxMulFac*sievePr }
sievePr := sievePr+sievePr;
Segment0 := sievePr div cMaxzahl;
Rest0 := sievePr-Segment0*cMaxzahl;
Segment0 := Segment0 * cRepFldLen;
Segment := Segment0;
Rest := Rest0;
with MulFeld[0] do
begin
dOfs := Rest0;
dSegment:= Segment0;
end;
for k := 1 to MaxMulFac shr 1-1 do
begin
Segment := Segment+Segment0;
Rest := Rest+Rest0;
IF Rest >= cMaxzahl then
Begin
Rest:= Rest-cMaxzahl;
Segment := Segment+cRepFldLen;
end;
with MulFeld[k] do
begin
dOfs := Rest;
dSegment:= Segment;
end;
end;
end;
procedure CalcDeltaNewPos(sievePr,MulPos:NativeUint);
var
Ofs,Segment,prevPos,actPos : Uint64;
i: NativeInt;
Begin
MulTab(sievePr);
//start at sqr sievePrime
CalcSqrOfs(Segment,Ofs);
NewStartPos := Segment+number[Ofs];
prevPos := NewStartPos;
deltaNewPos[0]:= prevPos;
For i := 0 to cRepFldLen-2 do
begin
inc(mulpos);
IF mulpos >= cRepFldLen then
mulpos := 0;
With MulFeld[DiffFld[mulpos]] do
begin
Ofs:= Ofs+dOfs;
Segment := Segment+dSegment;
end;
If Ofs >= cMaxZahl then
begin
Ofs := Ofs-cMaxZahl;
Segment := Segment+cRepFldLen;
end;
actPos := Segment+number[Ofs];
deltaNewPos[i]:= actPos - prevPos;
IF actPos> maxPos then
BREAK;
prevPos := actPos;
end;
deltaNewPos[cRepFldLen-1] := NewStartPos+cRepFldLen*sievePr-prevPos;
end;
procedure SieveByOnePrime(var sf:tsearchFld;sievePr:NativeUint);
var
pNewPos : ^Uint64;
pSiev0,
pSiev : ^tSievenum;// dynamic arrays are slow
Ofs : Int64;
Position : UINt64;
i: NativeInt;
Begin
pSiev0 := @sf[0];
Ofs := MaxPos-sievePr *cRepFldLen;
Position := NewStartPos;
{unmark multiples of sieve prime}
repeat
IF Position < Ofs then
Begin
pNewPos:= @deltaNewPos[0];
For i := Low(deltaNewPos) to High(deltaNewPos) do
Begin
pSiev := pSiev0;
inc(pSiev,Position DIV cBitSize);
//pSiev^ == @sf[Position DIV cBitSize]
pSiev^ := pSiev^ AND BitCLR[Position AND cAndMask];
inc(Position,pNewPos^);
inc(pNewPos);
end
end
else
Begin
pNewPos:= @deltaNewPos[0];
For i := Low(deltaNewPos) to High(deltaNewPos) do
Begin
IF Position >= MaxPos then
Break;
pSiev := pSiev0;
inc(pSiev,Position DIV cBitSize);
pSiev^ := pSiev^ AND BitCLR[Position AND cAndMask];
inc(Position,pNewPos^);
inc(pNewPos);
end
end;
until Position >= MaxPos;
end;
procedure SieveAll;
var
i,
sievePr,
PrimPos,
srPrPos : NativeUint;
l: Uint64;
Begin
Init;
MaxPos := CalcPos(MaxUpperLimit);
{start of prime sieving}
i := (MaxPos-1) DIV cBitSize+1;
setlength(searchFld,i);
IF Length(searchFld) <> i then
Begin
writeln('Not enough memory');
Halt(-227);
end;
For i := High(searchFld) downto 0 do
searchFld[i] := NativeUint(-1);
{the first prime}
srPrPos := 0;
PrimPos := 0;
sievePr := 1;
actSquare := sievePr;
repeat
{next prime}
inc(srPrPos);
i := 2*(DiffFld[PrimPos]+1);
//binom (a+b)^2; a^2 already known
actSquare := actSquare+(2*sievePr+i)*i;
inc(sievePr,i);
IF actSquare > MaxUpperLimit THEN
BREAK;
{if sievePr == prime then sieve with sievePr}
if BitSet[srPrPos AND cAndMask] AND
searchFld[srPrPos DIV cBitSize] <> 0then
Begin
write(sievePr:8,#8#8#8#8#8#8#8#8);
CalcDeltaNewPos(sievePr,PrimPos);
SieveByOnePrime(searchFld,sievePr);
end;
inc(PrimPos);
if PrimPos = cRepFldLen then
dec(PrimPos,PrimPos);// := 0;
until false;
end;
function InitRecPrime(pr: UInt64):tRecPrime;
var
svPos,sg : NativeUint;
Begin
svPos := CalcPos(pr);
sg := svPos DIV cRepFldLen;
with result do
Begin
rpsvPos := svPos;
rpSeg := sg;
rpOfs := svPos - sg*cRepFldLen;
rpPrime := RevIdx[rpOfs]+ sg*cMaxZahl;
end;
end;
function InitPrimeSvPos(svPos: Uint64):tRecPrime;
var
sg : LongWord;
Begin
sg := svPos DIV cRepFldLen;
with result do
Begin
rpsvPos := svPos;
rpSeg := sg;
rpOfs := svPos - sg*cRepFldLen;
rpPrime := RevIdx[rpOfs]+ sg*cMaxZahl;
end;
end;
function NextPrime(var pr: tRecPrime):Boolean;
var
ofs : LongWord;
svPos : Uint64;
Begin
with pr do
Begin
svPos := rpsvPos;
Ofs := rpOfs;
repeat
inc(svPos);
if svPos > MaxPos then
Begin
result := false;
EXIT;
end;
inc(Ofs);
IF Ofs >= cRepFldLen then
Begin
ofs := 0;
inc(rpSeg);
end;
until BitSet[svPos AND cAndMask] AND
searchFld[svPos DIV cBitSize] <> 0;
rpPrime := rpSeg*Uint64(cMaxZahl)+RevIdx[Ofs];
rpSvPos := svPos;
rpOfs := Ofs;
end;
result := true;
end;
function GetNthPrime(n: Uint64):tRecPrime;
var
i : longWord;
cnt: Uint64;
Begin
IF n > MaxPos then
EXIT;
i := 0;
cnt := Bis;
For i := 0 to n DIV cBitSize do
inc(cnt,PopCnt(NativeUint(searchFld[i])));
i := n DIV cBitSize+1;
while cnt < n do
Begin
inc(cnt,PopCnt(NativeUint(searchFld[i])));
inc(i);
end;
dec(i);
dec(cnt,PopCnt(NativeUint(searchFld[i])));
result := InitPrimeSvPos(i*Uint64(cBitSize)-1);
while cnt < n do
IF NextPrime(Result) then
inc(cnt)
else
Break;
end;
procedure ShowPrimes(loLmt,HiLmt: NativeInt);
var
p1 :tRecPrime;
Begin
IF HiLmt < loLmt then
exit;
p1 := InitRecPrime(loLmt);
while p1.rpPrime < LoLmt do
IF Not(NextPrime(p1)) Then
EXIT;
repeat
write(p1.rpPrime,' ');
IF Not(NextPrime(p1)) Then
Break;
until p1.rpPrime > HiLmt;
writeln;
end;
function CountPrimes(loLmt,HiLmt: NativeInt):LongWord;
var
p1 :tRecPrime;
Begin
result := 0;
IF HiLmt < loLmt then
exit;
p1 := InitRecPrime(loLmt);
while p1.rpPrime < LoLmt do
IF Not(NextPrime(p1)) Then
EXIT;
repeat
inc(result);
IF Not(NextPrime(p1)) Then
Break;
until p1.rpPrime > HiLmt;
end;
procedure WriteCntSmallPrimes(n: NativeInt);
var
i, p,prPos,svPos : nativeUint;
Begin
dec(n);
IF n < 0 then
EXIT;
write('First ',n+1,' primes ');
IF n < Bis then
Begin
For i := 0 to n do
write(InitPrim[i]:3);
end
else
Begin
For i := 0 to BIS do
write(InitPrim[i],' ');
dec(n,Bis);
svPos := 0;
PrPos := 0;
p := 1;
while n> 0 do
Begin
{next prime}
inc(svPos);
inc(p,2*(DiffFld[prPos]+1));
if BitSet[svPos AND cAndMask] AND searchFld[svPos DIV cBitSize] <>0 then
Begin
write(p,' ');
dec(n);
end;
inc(prPos);
if prPos = cRepFldLen then
dec(prPos,prPos);// := 0;
end;
end;
writeln;
end;
function RvsNumL(var n: Uint64):Uint64;
//reverse and last digit, most of the time n > base therefor repeat
const
base = 10;
var
q, c: Int64;
Begin
result := n;
q := 0;
repeat
c:= result div Base;
q := result+ (q-c)*Base;
result := c;
until result < Base;
n := q*Base+result;
end;
function IsEmirp(n:Uint64):boolean;
var
lastDgt:NativeUint;
ofs: NativeUint;
seg : Uint64;
Begin
seg := n;
lastDgt:= RvsNumL(n);
result:= false;
IF (seg = n) OR (n> MaxUpperLimit) then
EXIT;
IF lastDgt in [1,3,7,9] then
Begin
seg := n div cMaxZahl;
ofs := n-seg* cMaxzahl;//m mod cMaxZahl
IF (Number[ofs] <> 0) OR (ofs=1) then
begin
seg := seg *cRepFldLen+number[ofs];
result := BitSet[seg AND cAndMask] AND searchFld[seg DIV cBitSize] <> 0;
end
end;
end;
procedure GetEmirps(loLmt,HiLmt: Uint64);
var
p1 :tRecPrime;
cnt: NativeUint;
Begin
cnt := 0;
IF HiLmt < loLmt then
exit;
IF loLmt > MaxUpperLimit then
Exit;
IF HiLmt > MaxUpperLimit then
HiLmt := MaxUpperLimit;
p1 := InitRecPrime(loLmt);
while p1.rpPrime < LoLmt do
IF Not(NextPrime(p1)) Then
EXIT;
repeat
if isEmirp(p1.rpPrime) then
inc(cnt);
iF not(NextPrime(p1)) then
BREAK;
until p1.rpPrime > HiLmt;
write(cnt:10);
end;
var
T1,T0: TDateTime;
Anzahl :Uint64;
i,j : Uint64;
n : LongInt;
Begin
T0 := now;
SieveAll;
T1 := now;
writeln(' ');
Writeln('time for sieving ',FormatDateTime('NN:SS.ZZZ',T1-T0));
Anzahl := BIS;
For n := MaxPos DIV cBitSize-1 downto 0 do
inc(Anzahl,PopCnt(NativeUint(searchFld[n])));
n := MaxPos AND cAndMask;
IF n >0 then
Begin
dec(n);
repeat
IF BitSet[n] AND searchFld[MaxPos DIV cBitSize] <> 0 then
inc(Anzahl);
dec(n);
until n< 0;
end;
Writeln('there are ',Anzahl,' primes til ',MaxUpperLimit);
WriteCntSmallPrimes(20);
write('primes between 100 and 150: ');
ShowPrimes(100,150);
write('count of primes between 7700 and 8000 ');
Writeln(CountPrimes(7700,8000));
i := 100;
repeat
Writeln('the ',i, ' th prime ',GetNthPrime(i).rpPrime);
i := i * 10;
until i*25 > MaxUpperLimit;
writeln;
writeln('Count Emirps');
j := 10;
repeat
writeln(j:10);
GetEmirps( j, j+j-1);//10..00->19..99
GetEmirps(3*j,3*j+j-1);//30..00->39..99
GetEmirps(7*j,7*j+j-1);//70..00->79..99
GetEmirps(9*j,9*j+j-1);//90..00->99..99
writeln;
j:=j*10;
until j >= MaxUpperLimit;
end.
- output
//64-Bit time ./Prime9 time for sieving 02:26.176 there are 4118054813 primes til 99999999999 first 20 primes 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Primes between 100 and 150: 101 103 107 109 113 127 131 137 139 149 count of primes between 7700 and 8000 30 the 100 th prime 541 the 1000 th prime 7919 the 10000 th prime 104729 the 100000 th prime 1299709 the 1000000 th prime 15485863 the 10000000 th prime 179424673 the 100000000 th prime 2038074743 the 1000000000 th prime 22801763489 Count Emirps 1_0-1_9 3_0-3_9 7_0-7_9 9_0-9_9 10 1 1 3 1 //13/31 omitted 100 7 5 8 8 1000 60 51 43 50 10000 387 353 322 344 100000 2632 2422 2253 2231 1000000 18770 17751 17066 16887 10000000 141594 134894 130276 128814 100000000 1105560 1058667 1020020 1007777 1000000000 8838825 8485595 8188908 8106052 10000000000 72031835 69340410 67067391 66450596 real 8m11.174s user 8m10.517s sys 0m0.173s //32-Bit # time ./Prime9 time for sieving 03:07.562 there are 4118054813 primes til 99999999999 ... the 1000000000 th prime 22801763489 Count Emirps ... 10000000000 72031835 69340410 67067391 66450596 real 15m25.826s user 15m24.783s sys 0m0.180s test with trial division: Emirp primes between 300000000 and 400000000 : 1058667 rumtime for this: 2m 3 secs
Perl[edit]
Two examples of pure Perl extensible generators are shown in the Sieve of Eratosthenes#Extensible_sieves section.
The Math::Prime::Util module provides a highly performant, feature-rich library for generating, testing, and manipulating prime numbers in Perl. It offers full interoperability with Perl's bigint pragma.
Limits with a 64-bit Perl:
- nth_prime takes about 20 seconds to return the 10^14th prime and should be fast for all results up to ~4e17. It will be impractically slow past that.
- prime_count uses the LMO algorithm and takes about 35 seconds to return the count for primes to 10^16, and should have state of the art speed to 2^64-1. After that it will use a primality test in the interval so it still useful for large sizes with a small range.
- fast approximations and upper/lower limits are available, which should be fast for any input size including bigints.
- primes, next_prime, prev_prime, forprimes, prime_iterator, prime_iterator_object, and primality tests will work for practically any size input. The Math::Prime::Uti::GMP module is recommended for large inputs. With that module, these functions will work quickly for multi-thousand digit numbers.
use Math::Prime::Util qw(nth_prime prime_count primes);
# Direct solutions.
# primes([start],end) returns an array reference with all primes in the range
# prime_count([start],end) uses sieving or LMO to return fast prime counts
# nth_prime(n) does just that. It runs quite fast for native size inputs.
say "First 20: ", join(" ", @{primes(nth_prime(20))});
say "Between 100 and 150: ", join(" ", @{primes(100,150)});
say prime_count(7700,8000), " primes between 7700 and 8000";
say "${_}th prime: ", nth_prime($_) for map { 10**$_ } 1..8;
- Output:
First 20: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 30 primes between 7700 and 8000 10th prime: 29 100th prime: 541 1000th prime: 7919 10000th prime: 104729 100000th prime: 1299709 1000000th prime: 15485863 10000000th prime: 179424673 100000000th prime: 2038074743
There are many other ways, including prev_prime / next_prime, a simple iterator, an OO style iterator, a tied array, and a Pari-like forprimes construct. For example, the above example using the OO iterator:
use Math::Prime::Util "prime_iterator_object";
my $it = prime_iterator_object;
say "First 20: ", join(" ", map { $it->iterate() } 1..20);
$it->seek_to_value(100);
print "Between 100 and 150:";
print " ", $it->iterate() while $it->value() <= 150;
print "\n";
$it->seek_to_value(7700);
my $c = 0;
$c++ while $it->iterate() <= 8000;
say "$c primes between 7700 and 8000";
say "${_}th prime: ", $it->ith($_) for map { 10**$_ } 1..8;
Or using forprimes and a tied array:
use Math::Prime::Util qw/forprimes/;
use Math::Prime::Util::PrimeArray;
tie my @primes, 'Math::Prime::Util::PrimeArray';
say "First 20: @primes[0..19]"; # Slice from the tied array
print "Between 100 and 150: "; forprimes { print " $_"; } 100,150; print "\n";
# Count with forprimes
my $c = 0;
forprimes { $c++ } 7700,8000;
print "$c primes between 7700 and 8000\n";
# The tied array tries to do the right thing -- sieve a window if it sees
# forward or backward iteration, and nth_prime if it looks like random access.
say "${_}th prime: ", $primes[$_-1] for map { 10**$_ } 1..8;
Example showing bigints:
use bigint;
use Math::Prime::Util qw/forprimes prime_get_config/;
warn "No GMP, expect slow results\n" unless prime_get_config->{gmp};
my $n = 10**200;
forprimes { say $_-$n } $n,$n+1000;
- Output:
357 627 799
Perl 6[edit]
Build a lazy infinite list of primes using the Perl 6 builtin is-prime method. ( A lazy list will not bother to calculate the values until they are actually used. ) That is the first line. If you choose to calculate the entire list, it is fairly certain that you will run out of process / system memory before you finish... (patience too probably) but there aren't really any other constraints. The is-prime builtin uses a Miller-Rabin primality test with 100 iterations, so while it is not 100% absolutely guaranteed that every number it flags as prime actually is, the chances that it is wrong are about 4^{-100}. Much less than the chance that a cosmic ray will cause an error in your computers CPU. Everything after the first line is just display code for the various task requirements.
my @primes = lazy gather for 1 .. * { .take if $_.is-prime }
say "The first twenty primes:\n ", "[[email protected][^20].fmt("%d", ', ')}]";
say "The primes between 100 and 150:\n ", "[[email protected]&between(100, 150).fmt("%d", ', ')}]";
say "The number of primes between 7,700 and 8,000:\n ", +@primes.&between(7700, 8000);
say "The 10,000th prime:\n ", @primes[9999];
sub between (@p, $l, $u) {
gather for @p { .take if $l < $_ < $u; last if $_ >= $u }
}
- Output:
The first twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] The primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] The number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729
Python[edit]
The Croft spiral sieve prime generator from the Prime decomposition task is used which contains the lineislice(count(7), 0, None, 2)
The call to count(7)
is to a generator of integers that counts from 7 upwards with no upper limit set.
The definition croft
is a generator of primes and is used to generate as many primes as are asked for, in order.
from __future__ import print_function
from prime_decomposition import primes
from itertools import islice
def p_range(lower_inclusive, upper_exclusive):
'Primes in the range'
for p in primes():
if p >= upper_exclusive: break
if p >= lower_inclusive: yield p
if __name__ == '__main__':
print('The first twenty primes:\n ', list(islice(primes(),20)))
print('The primes between 100 and 150:\n ', list(p_range(100, 150)))
print('The ''number'' of primes between 7,700 and 8,000:\n ', len(list(p_range(7700, 8000))))
print('The 10,000th prime:\n ', next(islice(primes(),10000-1, 10000)))
- Output:
The first twenty primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] The primes between 100 and 150: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] The number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104729
210-wheel postponed incremental sieve[edit]
With more contemporary itertools use, 210-wheel incremental sieve with postponed primes processing and thus with radically reduced memory footprint which increases slower than square root of the number of primes produced:
def wsieve(): # ideone.com/mqO25A
wh11 = [ 2,4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10]
cs = accumulate( chain( [11], cycle( wh11)))
yield( next( cs)) # cf. ideone.com/WFv4f
ps = wsieve() # codereview.stackexchange.com/q/92365/9064
p = next(ps) # 11 stackoverflow.com/q/30553925/849891
psq = p*p # 121
D = dict( zip( accumulate( chain( [0], wh11)), count(0))) # start from
mults = {}
for c in cs:
if c in mults:
wheel = mults.pop(c)
elif c < psq:
yield c ; continue
else: # c==psq: map (p*) (roll wh from p) = roll (wh*p) from (p*p)
x = [p*d for d in wh11]
i = D[ (p-11) % 210]
wheel = accumulate( chain( [psq+x[i]], cycle( x[i+1:] + x[:i+1])))
p = next(ps) ; psq = p*p
for m in wheel:
if not m in mults:
break
mults[m] = wheel
def primes():
yield from (2, 3, 5, 7)
yield from wsieve()
print( list( islice( primes(), 0, 20)))
print( list( takewhile( lambda x: x<150,
dropwhile( lambda x: x<100, primes()))))
print( len( list( takewhile( lambda x: x<8000,
dropwhile( lambda x: x<7700, primes())))))
print( list( islice( primes(), 10000-1, 10000))[0])
- Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] [101, 103, 107, 109, 113, 127, 131, 137, 139, 149] 30 104729
Racket[edit]
Personal note: unless I need the raw power of an application-specific primes generator/filter,
I pretty well stick with the math/number-theory
library. And even when I write an ASPG/F I question
how it performs against the math/number-theory
version!
The link referenced in the source: math/number-theory
module documentation
#lang racket
;; Using the prime functions from:
(require math/number-theory)
(displayln "Show the first twenty primes.")
(next-primes 1 20)
(displayln "Show the primes between 100 and 150.")
;; Note that in each of the in-range filters I "add1" to the stop value, so that (in this case) 150 is
;; considered. I'm pretty sure it's not prime... but technology moves so fast nowadays that things
;; might have changed!
(for/list ((i (sequence-filter prime? (in-range 100 (add1 150))))) i)
(displayln "Show the number of primes between 7,700 and 8,000.")
;; (for/sum (...) 1) counts the values in a sequence
(for/sum ((i (sequence-filter prime? (in-range 7700 (add1 8000))))) 1)
(displayln "Show the 10,000th prime.")
(nth-prime (sub1 10000)) ; (nth-prime 0) => 2
;; If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a
;; system limit, (2^31 or memory overflow for example), then this may be used as long as an
;; explanation of the limits of the prime generator is also given. (Which may include a link
;; to/excerpt from, language documentation).
;;
;; Full details in:
;; [[http://docs.racket-lang.org/math/number-theory.html?q=prime%3F#%28part._primes%29]]
;; When reading the manual, note that "Integer" and "Natural" are unlimited (or bounded by whatever
;; big number representation there is (and the computational complexity of the work being asked).
(define 2^256 (expt 2 256))
2^256
(next-prime 2^256)
;; (Oh, and this is a 64-bit laptop, I left my 256-bit PC in the office.)
- Output:
Show the first twenty primes. (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) Show the primes between 100 and 150. (101 103 107 109 113 127 131 137 139 149) Show the number of primes between 7,700 and 8,000. 30 Show the 10,000th prime. 104729 115792089237316195423570985008687907853269984665640564039457584007913129639936 115792089237316195423570985008687907853269984665640564039457584007913129640233
REXX[edit]
Programming note: Most REXXes (of the 32-bit variety) run with an upper limit of roughly 2 Gbytes (for virtual storage), and that is the limit of this program (in building the stemmed array of prime numbers and prime number indicators, and available virtual storage will be the limiting factor of how many primes can be generated.
The method of extending primes (via the PRIMES subroutine) is of two kinds when invoking the PRIMES subroutine:
- a positive number which will (possibly) generate primes up to that total amount, and
- a negative number which will (possibly) generate primes up to |number|.
Two arrays are available to the caller after invoking the PRIMES subroutine. @.Nth where this is the Nth prime. Also, one can check if 1331 is a prime: !.1331 has the value of 1 (is prime), 0 (isn't prime).
For faster speed, the PRIMES subroutine's logic could be optimized a bit, as well as extending the initial list of low primes (and extending the fixed divisions to reduce the inner DO K loop (divisions of 3───►19).
/*REXX program calculates and displays primes using an extendible prime number generator*/
parse arg f .; if f=='' then f=20 /*allow specifying number for 1 ──► F.*/
call primes f; do j=1 for f; $=$ @.j; end /*j*/
say 'first' f 'primes are:' $
say
call primes -150; do j=100 to 150; if !.j==0 then iterate; $=$ j; end /*j*/
say 'the primes between 100 to 150 (inclusive) are:' $
say
call primes -8000; do j=7700 to 8000; if !.j==0 then iterate; $=$ j; end /*j*/
say 'the number of primes between 7700 and 8000 (inclusive) is:' words($)
say
call primes 10000
say 'the 10000th prime is:' @.10000
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
primes: procedure expose !. s. @. $ #; parse arg H . 1 m .,,$; H=abs(H)
if symbol('!.0')=='LIT' then /*1st time here? Then initialize stuff*/
do; !.=0; @.=0; s.=0 /*!.x = some prime; @.n = Nth prime. */
_=2 3 5 7 11 13 17 19 23 /*generate a bunch of low primes. */
do #=1 for words(_); p=word(_,#); @.#=p; !.p=1; end
#=#-1; !.0=#; s.#=@.#**2 /*set # to be the number of primes. */
end /* [↑] done with building low primes? */
neg= m<0 /*Negative? Request is for a P value.*/
if neg then if H<=@.# then return /*do we have a high enough P already?*/
else nop /*this is used to match the above THEN.*/
else if H<=# then return /*do we have a enough primes already ? */
/* [↓] gen more primes within range. */
do j=@.#+2 by 2 /*find primes until have H Primes. */
if j//3 ==0 then iterate /*is J divisible by three? */
parse var j '' -1 _; if _==5 then iterate /*is the right-most digit a 5?*/
if j//7 ==0 then iterate /*is J divisible by seven? */
if j//11==0 then iterate /*is J divisible by eleven? */
if j//13==0 then iterate /*is J divisible by thirteen? */
if j//17==0 then iterate /*is J divisible by seventeen? */
if j//19==0 then iterate /*is J divisible by nineteen? */
/*[↑] above five lines saves time. */
do k=!.0 while s.k<=j /*divide by the known odd primes. */
if j//@.k==0 then iterate j /*Is J ÷ by a prime? ¬prime. ___*/
end /*k*/ /* [↑] divide by odd primes up to √ j */
#=#+1 /*bump the number of primes found. */
@.#=j; s.#=j*j; !.j=1 /*assign to sparse array; prime²; P#.*/
if neg then if H<=@.# then leave /*do we have a high enough prime? */
else nop /*used to match the above THEN. */
else if H<=# then leave /*do we have enough primes yet? */
end /*j*/ /* [↑] keep generating until enough. */
return /*return to invoker with more primes. */
output when using the default inputs:
first 20 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 the primes between 100 to 150 (inclusive) are: 101 103 107 109 113 127 131 137 139 149 the number of primes between 7700 and 8000 (inclusive) is: 30 the 10000th prime is: 104729
Ring[edit]
see "first twenty primes : "
i = 1
nr = 0
while i <= 20
nr += 1
if isPrime(nr) see " " + nr i += 1 ok
end
see "primes between 100 and 150 : "
for nr = 100 to 150
if isPrime(nr) see " " + nr ok
next
see nl
see "primes between 7,700 and 8,000 : "
i = 0
for nr = 7700 to 8000
if isPrime(nr) i += 1 ok
next
see i + nl
see "The 10,000th prime : "
i = 1
nr = 0
while i <= 10000
nr += 1
if isPrime(nr) i += 1 ok
end
see nr + nl
func isPrime n
if n <= 1 return false ok
if n <= 3 return true ok
if (n & 1) = 0 return false ok
for t = 3 to sqrt(n) step 2
if (n % t) = 0 return false ok
next
return true
Output:
first twenty primes : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71pr primes between 100 and 150 : 101 103 107 109 113 127 131 137 139 149 primes between 7,700 and 8,000 : 30 The 10,000th prime : 104729
Ruby[edit]
The prime library behaves like an enumerator. It has an "each" method, which takes an upper bound as argument. This argument is nil by default, which means no upper bound.
require "prime"
puts Prime.take(20).join(", ")
puts Prime.each(150).drop_while{|pr| pr < 100}.join(", ")
puts Prime.each(8000).drop_while{|pr| pr < 7700}.count
puts Prime.take(10_000).last
- Output:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 30 104729
Seed7[edit]
The sieve of eratosthenes cannot be used, because it needs a limit. Instead the function getPrime is used. GetPrime generates all primes in sequence.
$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
result
var boolean: prime is FALSE;
local
var integer: count is 2;
begin
if number = 2 then
prime := TRUE;
elsif number > 2 then
while number rem count <> 0 and count * count <= number do
incr(count);
end while;
prime := number rem count <> 0;
end if;
end func;
var integer: currentPrime is 1;
var integer: primeNum is 0;
const func integer: getPrime is func
result
var integer: nextPrime is 0;
begin
repeat
incr(currentPrime);
until isPrime(currentPrime);
nextPrime := currentPrime;
incr(primeNum);
end func;
const proc: main is func
local
var integer: aPrime is 0;
var integer: count is 0;
begin
write("First twenty primes:");
while primeNum < 20 do
write(" " <& getPrime);
end while;
writeln;
repeat
aPrime := getPrime;
until aPrime >= 100;
write("Primes between 100 and 150:");
while aPrime <= 150 do
write(" " <& aPrime);
aPrime := getPrime;
end while;
writeln;
repeat
aPrime := getPrime;
until aPrime >= 7700;
while aPrime <= 8000 do
incr(count);
aPrime := getPrime;
end while;
writeln("Number of primes between 7,700 and 8,000: " <& count);
repeat
aPrime := getPrime;
until primeNum = 10000;
writeln("The 10,000th prime: " <& getPrime);
end func;
- Output:
First twenty primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Primes between 100 and 150: 101 103 107 109 113 127 131 137 139 149 Number of primes between 7,700 and 8,000: 30 The 10,000th prime: 104743
Sidef[edit]
var nt = frequire('ntheory')
say ("First 20: ", nt.primes(nt.nth_prime(20)).join(' '))
say ("Between 100 and 150: ", nt.primes(100,150).join(' '))
say (nt.prime_count(7700,8000), " primes between 7700 and 8000")
say ("10,000th prime: ", nt.nth_prime(10_000))
- Output:
First 20: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 Between 100 and 150: 101 103 107 109 113 127 131 137 139 149 30 primes between 7700 and 8000 10,000th prime: 104729
Tcl[edit]
package require Tcl 8.6
# An iterative version of the Sieve of Eratosthenes.
# Effective limit is the size of memory.
coroutine primes apply {{} {
yield
while 1 {yield [coroutine primes_[incr p] apply {{} {
yield [info coroutine]
set plist {}
for {set n 2} true {incr n} {
set found 0
foreach p $plist {
if {$n%$p==0} {
set found 1
break
}
}
if {!$found} {
lappend plist $n
yield $n
}
}
}}]}
}}
set p [primes]
for {set primes {}} {[llength $primes] < 20} {} {
lappend primes [$p]
}
puts 1st20=[join $primes ,]
rename $p {}
set p [primes]
for {set primes {}} {[set n [$p]] <= 150} {} {
if {$n >= 100 && $n <= 150} {
lappend primes $n
}
}
puts 100-150=[join $primes ,]
rename $p {}
set p [primes]
for {set count 0} {[set n [$p]] <= 8000} {} {
incr count [expr {$n>=7700 && $n<=8000}]
}
puts count7700-8000=$count
rename $p {}
set p [primes]
for {set count 0} {$count < 10000} {incr count} {
set prime [$p]
}
puts prime10000=$prime
rename $p {}
- Output:
1st20=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71 100-150=101,103,107,109,113,127,131,137,139,149 count7700-8000=30 prime10000=104729
zkl[edit]
// http://stackoverflow.com/revisions/10733621/4
fcn postponed_sieve(){ # postponed sieve, by Will Ness
vm.yield(2); vm.yield(3); # original code David Eppstein,
vm.yield(5); vm.yield(7); # ActiveState Recipe 2002
D:=Dictionary();
ps:=Utils.Generator(postponed_sieve); # a separate Primes Supply:
p:=ps.pump(2,Void); # (3) a Prime to add to dict
q:=p*p; # (9) when its sQuare is
c:=9; # the next Candidate
while(1){
if (not D.holds(c)){ # not a multiple of any prime seen so far:
if (c < q) vm.yield(c); # a prime, or
else{ # (c==q): # the next prime's square:
add(D,c + 2*p,2*p); # (9+6,6 : 15,21,27,33,...)
p=ps.next(); # (5)
q=p*p; # (25)
}
}else{ # 'c' is a composite:
s := D.pop(c); # step of increment
add(D,c + s,s); # next multiple, same step
}
c += 2; # next odd candidate
}
}
fcn add(D,x,s){ # make no multiple keys in Dict
while(D.holds(x)){ x += s } # increment by the given step
D[x] = s;
}
primes:=Utils.Generator(postponed_sieve);
primes.walk(20).println(); // first 20 primes
primes.pump(List,fcn(p){ // the primes between 100 & 150
if (p<100) Void.Skip else if(p>150) Void.Stop else p
}).println();
primes.reduce(fcn(n,p){ // count of primes between 7700 & 8000
if (p<=7700) n else if(p>8000) Void.Stop else n+1
},0).println();
primes=Utils.Generator(postponed_sieve); // new Generator
primes.drop(0d9_999); primes.next().println(); // 10,000th prime
// or to carry on until the 100,000th:
primes.pump(Void,'wrap(p){ primes.n<=0d100_000 and p or Void.Stop }).println();
- Output:
L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71) L(101,103,107,109,113,127,131,137,139,149) 30 104729 1299709
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), this is a direct drop in for the above:
var [const] BN=Import("zklBigNum"); // libGMP
bigPrimes:=Walker(fcn(p){ p.nextPrime().copy(); }.fp(BN(1)));
For example:
bigPrimes.walk(20).println(); // first 20 primes
bigPrimes.pump(Void,'wrap(p){ bigPrimes.n<=0d10_000 and p or Void.Stop }).println();
- Output:
L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71) 104729