Extensible prime generator: Difference between revisions
(Use a generator instead of the sieve of eratosthenes) |
GordonBGood (talk | contribs) |
||
| Line 585: | Line 585: | ||
The 10,000th prime: |
The 10,000th prime: |
||
104729</pre> |
104729</pre> |
||
The above works fine although slowly for Pythod 3 which has an only Integer type which is infinite precision (subject only to available memory) but only works for prime ranges above 46349 if the integers are the long (L) type which is then the same as the default integer type for Python 3. It is actually quite a poor algorithm in that it does not postpone the adding of the prime culling sequences to the Priority Queue until needed nor is the Priority Queue the best choice for large ranges in that it suffers from a log n (or log square root of n if properly postponed) instead of the linear amortized access for a hash table based dictionary. |
|||
For an extensible range prime generator it would be better to use one of the following implementations where the adding of culling sequences is postponed and which use the dictionary type. |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Revision as of 12:58, 22 June 2014
You are encouraged to solve this task according to the task description, using any language you may know.
The task is to 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, (231 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).
Ada
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.
<lang Ada>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;</lang>
- 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
<lang AutoHotkey>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 } }</lang>
- 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
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. <lang c>#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;
}</lang>
- 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
D
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. <lang d>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));
}</lang>
- 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
Go
<lang go>package main
import "fmt"
func newP() func() int {
n := 1 // open-ended counter
return func() int {
for {
n++ // count without limit
for f := 2; ; f++ {
if f == n {
return n
}
if n%f == 0 {
break
}
}
}
}
}
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())
}</lang>
- 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
Icon and Unicon
Only works in Unicon (use of the Heap class). Brute force.
The expression: <lang unicon>![2,3,5,7] | (nc := 11) | (nc +:= |wheel2345)</lang> is an open-ended sequence generating potential primes.
<lang unicon>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</lang>
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
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)".
<lang J> 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</lang>
Perl
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.
<lang perl>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;</lang>
- 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: <lang perl>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;</lang> Or using forprimes and a tied array: <lang perl>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;</lang>
Example showing bigints: <lang perl>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;</lang>
- Output:
357 627 799
Perl 6
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.
<lang perl6>my @primes := gather for 1 .. * { .take if $_.is-prime }
say "The first twenty primes:\n ", "[{@primes[^20].fmt("%d", ', ')}]"; say "The primes between 100 and 150:\n ", "[{@primes.&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 }
}</lang>
- 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
The Croft spiral sieve prime generator from the Prime decomposition task is used which contains the line <lang python>islice(count(7), 0, None, 2)</lang>
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.
<lang python>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)))</lang>
- 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
Alternately, we can use the much simpler infinite primes generator from Sieve of Eratosthenes#Infinite generator. It doesn't have an upper limit; it has an infinite loop (while True:) in the generator function and will keep on generating as many as needed.
<lang python>from __future__ import print_function from sieve_of_eratosthenes_infinite_generator import sieve from itertools import islice
def p_range(lower_inclusive, upper_exclusive):
'Primes in the range'
for p in sieve():
if p >= upper_exclusive: break
if p >= lower_inclusive: yield p
if __name__ == '__main__':
print('The first twenty primes:\n ', list(islice(sieve(),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(sieve(),10000-1, 10000)))</lang>
- 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
The above works fine although slowly for Pythod 3 which has an only Integer type which is infinite precision (subject only to available memory) but only works for prime ranges above 46349 if the integers are the long (L) type which is then the same as the default integer type for Python 3. It is actually quite a poor algorithm in that it does not postpone the adding of the prime culling sequences to the Priority Queue until needed nor is the Priority Queue the best choice for large ranges in that it suffers from a log n (or log square root of n if properly postponed) instead of the linear amortized access for a hash table based dictionary.
For an extensible range prime generator it would be better to use one of the following implementations where the adding of culling sequences is postponed and which use the dictionary type.
Racket
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>#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
- [[1]]
- 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.)</lang>
- 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
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 subrlutine. @.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). <lang rexx>/*REXX program finds primes using an extendible prime number generator.*/ parse arg f .; if f== then f=20 /*allow specifying # for 1 ──► F.*/ call primes f; do j=1 for f; $=$ @.j; end say 'first' f 'primes are:' $ say call primes -150; do j=100 to 150; if !.j==0 then iterate; $=$ j; end 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 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 done.*/ /*──────────────────────────────────PRIMES subroutine───────────────────*/ primes: procedure expose !. s. @. $ #; parse arg H . 1 m .,,$; H=abs(H) if symbol('!.0')=='LIT' then /*1st time here? 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 number of primes.*/
end /* [↑] done with building low Ps*/
neg= m<0 /*Neg? Request is for a P value.*/ if neg then if H<=@.# then return /*Have a high enough P already?*/
else nop /*used to match the above THEN. */
else if H<=# then return /*Have a enough primes already ? */
/*─────────────────────────────────────── [↓] gen more P's within range*/
do j=@.#+2 by 2 /*find primes until have H Primes*/
if j//3 ==0 then iterate /*is J divisible by three? */
if right(j,1)==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 seven 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 divisible by P? Not prime.*/
end /*k*/ /* [↑] divide by odd primes √j.*/
#=#+1 /*bump number of primes found. */
@.#=j; s.#=j*j; !.j=1 /*assign to sparse array; prime².*/
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 'til nuff*/
return /*return to invoker with more Ps.*/</lang> 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
Ruby
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. <lang ruby>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</lang>
- 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
The sieve of eratosthenes cannot be used, because it needs a limit. Instead the function getPrime is used. GetPrime generates all primes in sequence. <lang seed7>$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
result
var boolean: result is FALSE;
local
var integer: count is 2;
begin
if number = 2 then
result := TRUE;
elsif number > 2 then
while number rem count <> 0 and count * count <= number do
incr(count);
end while;
result := 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: prime is 0;
begin
repeat
incr(currentPrime);
until isPrime(currentPrime);
prime := 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;</lang>
- 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
Tcl
<lang tcl>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 {}</lang>
- 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
fcn postponed_sieve(){ # postponed sieve, by Will Ness
vm.yield(2); vm.yield(3); # original code David Eppstein,
vm.yield(5); vm.yield(7);
D:=Dictionary(); # ActiveState Recipe 2002
ps:=Utils.Generator(postponed_sieve); # a separate Primes Supply:
p:=ps.pump(2,False); # (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;
}</lang> <lang zkl>var primes = Utils.Generator(postponed_sieve); primes.walk(20).println(); // first 20 primes
primes.pump(List,fcn(p){ // primes between 100 & 150
if (p<100) Void.Skip else if(p>150) Void.Stop else p
}); 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); primes = Utils.Generator(postponed_sieve); // 10,000th prime primes.drop(0d9_999); primes.next().println();
// or to carry on until the 100,000th:
primes.pump(Void,fcn(p){primes._n < 0d100_000 and p or Void.Stop}).println(); </lang>
- 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