Extensible prime generator: Difference between revisions

'''Note 2:''' If a languages in-built prime generator is extensible or is guaranteed to generate primes up to a system limit, (2³¹ 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).

 

<br>

 

<br>

 

=={{header|Ada}}==

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.

 

 

procedure Prime_Gen is

"th prime:");

end;

 

{{out}}

 

=={{header|AutoHotkey}}==

p := 1 ;p functions as the counter

Loop, 10000 {

return, 1

}

{{Output}}

<pre>First twenty primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

Number of primes between 7,700 and 8,000: 30

The 10,000th prime: 104729</pre>

 

=={{header|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.

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>

* ~100,000,000 primes is about the limits of this algorithm. This version is not as idiomatic to C as a page-segmented sieve would be.

 

#include <stdio.h>

#include <stdlib.h>

return 0;

}

{{Out}}

<pre>

Based on "The Genuine Sieve of Eratosthenes" by Melissa E. O'Neill.

UPDATE: Added wheel optimization to match its C counterpart.

#include <cstdint>

#include <queue>

}

return 0;

 

{{out}}

This is a "segmented sieve" implementation inspired by the original C solution.

Execution time is about 4 seconds on my system (macOS 10.15.4, 3.2GHz Quad-Core Intel Core i5).

#include <iostream>

#include <cmath>

}

return 0;

 

{{out}}

=={{header|Clojure}}==

 

(:gen-class)

(:require [clojure.string :as string]))

 

 

{{out}}

<pre>

 

The above version is adequate for ranges up to the low millions, so covers the task requirements of primes up to just over a hundred thousands easily. However, it has a O(n^(3/2)) performance which means that it gets slow quite quickly with range as compared to a true incremental Sieve of Eratosthenes, which has O(n (log n)) performance. The following code is about the same speed for ranges in the low millions but quickly passes the above code in speed for large ranges to where it only takes 10's of seconds for a range of a hundred million where the above code takes thousands of seconds. The code is based on the Richard Bird list based Sieve of Eratosthenes mentioned in the O'Neil article but has infinite tree folding added as well as wheel factorization so that it is about the same speed and performance as a Sieve of Eratosthenes based on a priority queue; the code is written here in purely functional form with no mutation, as follows:

clojure.lang.ISeq

(first [_] v)

(if (<= i 0)

(->CIS (get wheel-primes 0) ff)

 

Now these functional incremental sieves are of limited use if one requires ranges of billions as they are hundreds of times slower than a version of a bit-packed page-segmented mutable array Sieve of Eratosthenes, which for Clojure there is a version at the end of Clojure [[Sieve_of_Eratosthenes#Unbounded_Versions]] section on the Sieve of Eratosthenes task page; this version will handle ranges of a billion in seconds rather than hundreds of seconds.

 

=={{header|D}}==

This uses a Prime struct defined in the [[Sieve of Eratosthenes#Extensible Version|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.

import std.stdio, std.range, std.algorithm, sieve_of_eratosthenes3;

 

.filter!q{a > 7_699}.walkLength);

writeln("10,000th prime: ", prime(9_999));

{{out}}

<pre>First twenty primes:

 

===Faster Alternative Version===

 

import std.container: Array, BinaryHeap, RedBlackTree;

LazyPrimeSieve().until!q{a > 8_000}.filter!q{a > 7_699}.walkLength);

writeln("10,000th prime: ", LazyPrimeSieve().dropExactly(9999).front);

{{out}}

<pre>Sum of first 100,000 primes: 62260698721

A version based on a (hashed) Map:

 

Iterable<int> oddprms() sync* {

yield(3); yield(5); // need at least 2 for initialization

final answer = primesMap().takeWhile((p)=>p<2000000).reduce((a,p)=>a+p);

final elapsed = DateTime.now().millisecondsSinceEpoch - start;

{{output}}

<pre>The first 20 primes:

 

It solves the Euler Problem 10 in almost too short a time to be measured, and it becomes useful for ranges of hundreds of thousands. It can count all the primes to a billion on the low end tablet CPU of an Intel x5-Z8350 at 1.92 Gigahertz used to develop this in 40 seconds but using a generator slows the performance and it can use the provided `countPrimesTo` function to do the job four times as fast by directly manipulating the provided iteration of sieved bit-packed arrays.

 

=={{header|EchoLisp}}==

Standard prime functions handle numbers < 2e+9. See [http://www.echolalie.org/echolisp/help.html#prime?] . The '''bigint''' library handles large numbers. See [http://www.echolalie.org/echolisp/help.html#bigint.lib]. The only limitations are time, memory, and browser performances ..

; the first twenty primes

(primes 20)

(prime? (1+ (factorial 116))) → #t

 

 

=={{header|Elixir}}==

 

The [[Sieve_of_Eratosthenes#Elixir]] Task page lists two "infinite" extensible generators at the bottom. The first of those, using a (hash) Map is reproduced here along with the code to fulfill the required tasks:

@typep stt :: {integer, integer, integer, Enumerable.integer, %{integer => integer}}

 

:timer.tc(testfunc)

|> (fn {t,_} ->

{{output}}

<pre>The first 20 primes are:

=={{header|F_Sharp|F#}}==

This task uses [http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Unbounded_Page-Segmented_Bit-Packed_Odds-Only_Mutable_Array_Sieve Unbounded_Page-Segmented_Bit-Packed Odds-Only Mutable Array Sieve F#]

let isPrime64 g=if g<2L then false else let mx=int(sqrt(float g)) in pCache|>Seq.takeWhile(fun n->n<=mx)|>Seq.forall(fun n->g%(int64 n)>0L)

 

===The Task===

{{out}}

<pre>

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

</pre>

{{out}}

<pre>

101 103 107 109 113 127 131 137 139 149

</pre>

{{out}}

<pre>

</pre>

To demonstrate extensibility I find the 10000th prime.

Seq.item 9999 pCache

{{out}}

<pre>

</pre>

I then find the 10001st prime which takes less time.

Seq.item 10000 pCache

{{out}}

<pre>

val it : int = 104743

</pre>

( primesSeq() |> Seq.take 20

|> Seq.fold (fun s p -> s + string p + " ") "" )

printfn "The %dth prime is: %A" n (primesSeq() |> Seq.item (n - 1))

let timed = (System.DateTime.Now.Ticks - strt) / 10000L

{{out}}

<pre>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

 

Factor's <code>fixnums</code> automatically promote to <code>bignums</code> when large enough, so there are no limits to its prime generator other than the capabilities of the machine it's running on.

 

"First 20 primes: " write

 

"10,000th prime: " write

{{out}}

<pre>

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 <code>INTEGER</code> were to be replaced by <code>INTEGER*8</code> though not all variables need be changed - such as <code>C</code> and <code>B</code> 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...

 

DO WHILE(F <= LST/F) !Except, LST might also overflow the integer limit, so

DO WHILE(F <= (IST + 2*(SBITS - 1))/F) !Which becomes...

Except, <code>IST</code> might overflow the integer limit, in which case function PSURGE declares itself unable to proceed and returns ''false''.

 

Although recursion is now permissible if one utters the magic word <code>RECURSIVE</code>, 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 for one, and "free"-format for the other) 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.

 

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.

END DO !On to the next in the list.

 

DO WHILE (P.LE.150)

...stuff...

P = NEXTPRIME(P)

 

===The Results===

 

The thinning out rather suggests an alternative encoding such as by counting the number of "off" bits until the next "on" bit, but this would produce a variable-length packing so that it would no longer be easy to find the bit associated with a given number by something so simple as <code>R = (NN - SORG)/(2*SBITS)</code> as in NEXTPRIME. 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.

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

 

 

 

 

 

 

 

</pre>

 

=={{header|Go}}==

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.

 

import (

*p = q[:last]

return e

{{out}}

<pre>

Due to how Go's imports work, the bellow can be given directly to "<code>go run</code>" or "<code>go build</code>" 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.)

 

import (

}

fmt.Println("10,000th prime:", p.Next())

 

=={{header|Haskell}}==

This program uses the [http://hackage.haskell.org/package/primes primes] package, which uses a lazy wheel sieve to produce an infinite list of primes.

 

 

import Data.List

print $ genericLength $ primesBetweenInclusive 7700 8000

putStr "The 10000th prime: "

 

{{out}}

Using list based unbounded sieve from [[Sieve_of_Eratosthenes#With_Wheel|here]] (runs instantly):

 

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

 

 

λ> (!! (10000-1)) primesW

 

==Icon and {{header|Unicon}}==

 

The expression:

is an open-ended sequence generating potential primes.

 

record filter(composite, prime) # next composite involving this prime

 

 

# Provide a function for comparing filters in the priority queue...

 

{{out}}

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)".

 

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

30

p:10000-1

 

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

 

 

=={{header|Java}}==

Based on my second C++ solution, which in turn was based on the C solution.

 

public class PrimeGenerator {

}

}

 

{{out}}

Sounds a bit weird, but I hope it will be intelligible by the testing examples below. First the code:

 

var i,

arr = [];

// (surrogate for a quite long and detailed try-catch-block anywhere before)

throw("Invalid arguments for primeGenerator()");

 

'''Test'''

console.log(primeGenerator(20, true));

 

 

// the 10,000th prime

 

'''Output'''

 

Array [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 ]

30

 

 

=={{header|jq}}==

 

'''Preliminaries:'''

# until/2 loops until cond is satisfied,

# and emits the value satisfying the condition:

_until;

 

 

'''Prime numbers:'''

# "previous" must be the array of sorted primes greater than 1 up to (.|sqrt)

def is_prime(previous):

def primes_upto(n):

until( .[length-1] > n; extend_primes )

'''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.

 

"Primes between 100 and 150:",

 

(( primes_upto(8000) | count( . > 7700) | length) as $length

{{out}}

First 20 primes:

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

The 10,000th prime is 104729

 

 

=={{header|Julia}}==

and by default determines primes with Knuth's recommended level for cryptography of an error less than

(0.25)^25 = 8.881784197001252e-16, or 1 in 1125899906842624.

 

sum = 2

println("the primes between 100 and 150 are ", primes(100,150))

println("The number of primes between 7,700 and 8,000 is ", length(primes(7700, 8000)))

{{output}}

<pre>

 

The above code just uses the "Primes" package as a set of tools to solve the tasks. The following code creates a very simple generator using `isprime` inside a iterator and then uses that to solve the tasks:

 

PrimesGen() = Iterators.filter(isprime, Iterators.countfrom(Int64(2)))

end

println("The 10,000th prime: ", Iterators.first(Iterators.drop(PrimesGen(), 9999)))

 

This outputs:

 

To show it's speed, lets use it to solve the Euler Problem 10 of calculating the sum of the primes to two million as follows:

@time let sm = 0

for p in Iterators.filter(isprime, Iterators.countfrom(UInt64(2)))

p > 2000000 && break

sm += p

 

which outputs:

 

The above code is more than adequate to solve the trivial tasks as required here, but is really too slow for "industrial strength" tasks for ranges of billions. The following code uses the Page Segmented Algorithm from [[Sieve_of_Eratosthenes#Julia]] to solve the task:

 

print("Sum of first 100,000 primes: ")

end; println("Number of primes between 7700 and 8000: ", cnt)

end

 

to produce the same output much faster.

 

To show how much faster it is, doing the same Euler Problem 10 as follows:

@time let sm = 0

for p in PrimesPaged()

p > 2000000 && break

sm += p

 

produces:

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.

((workwith|Kotlin|version 1.3}}

if (n < 2) return false

if (n % 2 == 0) return n == 2

println("Number of primes between 7700 and 8000 = ${primes.filter { it in 7700..8000 }.count()}")

println("10,000th prime = ${primes.last()}")

 

{{out}}

 

The following odds-only incremental Sieve of Eratosthenes generator has O(n log (log n)) performance due to using a (mutable) HashMap:

yield(2)

fun oddprms(): Sequence<Int> = sequence {

}

yieldAll(oddprms())

 

it is faster than the first example even though not using wheel factorization (other than odds-only) and rapidly pulls far ahead of it with increasing range such that it is usable to a range of 100 million in the order of 10 seconds.

 

It can count the primes to one billion in about 15 seconds on a slow tablet CPU (Intel x5-Z8350 at 1.92 Gigahertz) with the following code:

 

Further speed-ups can be achieved of about a factor of four with maximum wheel factorization and by multi-threading by the factor of the effective number of cores used, but there is little point when most of the execution time as a generator is spend iterating over the results.

=={{header|Lua}}==

The modest requirements of this task allow for naive implementations, such as what follows. This generator does not even use its own list of primes to help determine subsequent primes! (though easily fixed) So, it it sufficient, but not efficient.

count_limit = 2,

value_limit = 3,

needmore = function(self)

return (self.count_limit ~= nil and #self.primelist < self.count_limit)

end,

generate = function(self, count_limit, value_limit)

 

primegen:generate(100000, nil)

{{out}}

<pre>First 20 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

The following script implements a Sieve of Eratosthenes that is automatically extended when a method call needs a higher upper limit.

 

property _sieve

 

end repeat

end repeat

 

put "First twenty primes: " & sieve.getNPrimes(20)

put "Primes between 100 and 150: "& sieve.getPrimesInRange(100, 150)

put "Number of primes between 7,700 and 8,000: " & sieve.getPrimesInRange(7700, 8000).count

 

{{out}}

Loop statement check a flag in a block of code ({ }), so when the block ends restart again (resetting the loop flag)

 

Module CheckPrimes {

\\ Inventories are lists, Known and Known1 are pointers to Inventories

}

CheckPrimes

{{out}}

<pre>

I use same indentation so you can copy it at same position as in example above. A loop statement mark once the current block for restart after then last statement on block.

 

PrimeNth=lambda Known, Known1 (n as long) -> {

if n<1 then Error "Only >=1"

x++ : Loop }

}

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

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.

{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]

30

Prime[10000]

 

=={{header|Nim}}==

 

For such trivial ranges as the task requirements or solving the Euler Problem 10 of summing the primes to two million, a basic generator such as the hash table based version from the [[Sieve_of_Eratosthenes#Nim_Unbounded_Versions]] section of the Sieve of Eratosthenes task will suffice, as follows:

 

type PrimeType = int

echo "The sum of the primes to two million is: ", sum

break

{{output}}

<pre>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

 

To use that sieve, just substitute the following in the code:

 

wherever the following is in the code:

and one doesn't need the lines including `iter` just above these lines at all.

 

As noted in that section, using an extensible generator isn't the best choice for huge ranges as much higher efficiency can be obtained by using functions that deal directly with the composite culled packed-bit array representations directly as the `countPrimesTo` function does. This makes further improvements to the culling efficiency pointless, as even if one were to reduce the culling speed to zero, it still would take several seconds per range of a billion to enumerate the found primes as a generator.

 

 

PARI includes a nice prime generator which is quite extensible:

showprimes(GEN lower, GEN upper)

{

pari_printf("%Ps\n", T.pp);

}

 

Most of these functions are already built into GP:

primes([100,150])

#primes([7700,8000]) /* or */

s=0; forprime(p=7700,8000,s++); s

 

=={{header|Pascal}}==

{{works with|Free Pascal}}

First the unit.Still a work in progress.

 

./primesieve -t1 100000071680 Sieve size = 256 KiB Threads = 1 100%

Seconds: 19.891 Primes: 4118057696

unit primsieve;

{$IFDEF FPC}

{$IFEND}

{segmented sieve of Erathostenes using only odd numbers}

function SieveSize :LongInt;

function Nextprime: Uint64;

function TotalCount :Uint64;

function PosOfPrime: Uint64;

{$ALIGN 32}

//prime = FoundPrimesOffset + 2*FoundPrimes[0..FoundPrimesCnt]

{$ALIGN 32}

sievePrimes : array[0..78498] of tSievePrim;// 1e6^2 ->1e12

FoundPrimesOffset : Uint64;

FoundPrimesCnt,

function InsertSievePrimes(PrimPos:NativeInt):NativeInt;

var

begin

i := 0;

i := maxPreSievePrimeNum;

pr :=0;

with sievePrimes[PrimPos] do

Begin

pr := FoundPrimes[i]*2+1;

end;

inc(PrimPos);

for i := i+1 to FoundPrimesCnt-1 do

Begin

pr := FoundPrimes[i]*2+1;

end;

inc(PrimPos);

end;

result := PrimPos;

end;

SieveNum :=0;

CopyPreSieveInSieve;

i := 1; // start with 3

repeat

CollectPrimes;

PrimPos := InsertSievePrimes(0);

IF PrimPos < High(sievePrimes) then

repeat

sieveOneBlock;

dec(SieveNum);

PrimPos := InsertSievePrimes(PrimPos);

inc(SieveNum);

Init0Sieve;

end;

procedure CollectPrimes;

//extract primes to FoundPrimes

var

pSieve : pbyte;

i,idx : NativeUint;

Begin

FoundPrimesIdx := 0;

pFound :=@FoundPrimes[0];

end;

 

begin

CopyPreSieveInSieve;

end;

 

Begin

SieveOneBlock;

end;

 

Begin

result := FoundPrimesTotal-FoundPrimesCnt+FoundPrimesIdx;

end;

 

begin

result := FoundPrimesTotal;

end;

 

Begin

result := 2*cSieveSize;

end;

 

Begin

result := (SieveNum-1)*2*cSieveSize;

end;

 

Begin

Init0Sieve;

InitPrime;

end.

 

;the test program:

program test;

uses

primsieve;

var

Begin

repeat

inc(cnt);

</pre>

 

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.

{$IFDEF FPC}

{$MODE DELPHI}

dgtCnt := 0;

until j >= MaxUpperLimit;

;output:

<pre>//64-Bit

* <tt>primes</tt>, <tt>next_prime</tt>, <tt>prev_prime</tt>, <tt>forprimes</tt>, <tt>prime_iterator</tt>, <tt>prime_iterator_object</tt>, and primality tests will work for practically any size input. The [https://metacpan.org/pod/Math::Prime::Util::GMP Math::Prime::Uti::GMP] module is recommended for large inputs. With that module, these functions will work quickly for multi-thousand digit numbers.

 

# Direct solutions.

# primes([start],end) returns an array reference with all primes in the range

say "Between 100 and 150: ", join(" ", @{primes(100,150)});

say prime_count(7700,8000), " primes between 7700 and 8000";

{{out}}

<pre>First 20: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

 

There are many other ways, including <tt>prev_prime</tt> / <tt>next_prime</tt>, a simple iterator, an OO style iterator, a tied array, and a Pari-like <tt>forprimes</tt> construct. For example, the above example using the OO iterator:

my $it = prime_iterator_object;

say "First 20: ", join(" ", map { $it->iterate() } 1..20);

$c++ while $it->iterate() <= 8000;

say "$c primes between 7700 and 8000";

Or using forprimes and a tied array:

use Math::Prime::Util::PrimeArray;

tie my @primes, 'Math::Prime::Util::PrimeArray';

# 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.

 

Example showing bigints:

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;

{{out}}

<pre>

Some further discussion of this can be found on my talk page --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]])

 

 

{{Out}}

<pre>

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}

27.578

</pre>

 

=={{header|PicoLisp}}==

(let S (sqrt N)

(for D Lst

N

"th prime: "

{{out}}

<pre>First 20 primes: (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)

===Faster version using a priority queue sieve and 2357 wheel===

This version runs about twice as quickly by using the method above to find small primes as a base for populating the priority queues required for the lazy sieve of Eratosthenes algorithm by Melissa O'Neil.

(load "plcommon/pairing-heap.l") # Pairing heap from RC task "Priority Queue"

 

Q (* P P)

H (heap-insert (cons Q Wp P) H))))))))))

Driver code:

(prin "The first 20 primes: ")

(do 20 (printsp (primes T)))

(prinl (align 9 (comma_fmt N)) " " (align 12 (comma_fmt (nthprime N)))))

(bye)

{{Out}}

<pre>

 

=={{header|PureBasic}}==

DisableDebugger

Define StartTime.i=ElapsedMilliseconds()

Print(~"\nRuntime milliseconds: "+

Str(ElapsedMilliseconds()-StartTime))

{{out}}

<pre>First twenty: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

 

===Python: Croft spiral===

The call to <code>count(7)</code> is to a generator of integers that counts from 7 upwards with no upper limit set.<br>

The definition <code>croft</code> is a generator of primes and is used to generate as many primes as are asked for, in order.

 

from prime_decomposition import primes

from itertools import islice

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))))

 

{{out}}

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:

 

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,

ps = wsieve() # codereview.stackexchange.com/q/92365/9064

p = next(ps) # 11 stackoverflow.com/q/30553925/849891

psq = p*p # 121

mults = {}

for c in cs:

if c in mults:

else: # c==psq: map (p*) (roll wh from p) = roll (wh*p) from (p*p)

x = [p*d for d in wh11]

break

mults[m] = wheel

 

 

print( list( islice( primes(), 0, 20)))

dropwhile( lambda x: x<100, primes()))))

dropwhile( lambda x: x<7700, primes())))))

 

{{out}}

After a [[https://paddy3118.blogspot.com/2018/11/to-infinity-beyond.html?showComment=1541671062388#c8979782377032256564 blog entry]] on implementing a particular Haskell solution in Python.

 

 

def prime_sieve():

sum(1 for x in takewhile(leq_8000, prime_sieve()) if x >= 7700))

print("Show the 10,000th prime.\n =",

 

{{out}}

The link referenced in the source: [http://docs.racket-lang.org/math/number-theory.html?q=prime%3F#%28part._primes%29 <code>math/number-theory</code> module documentation]

 

;; Using the prime functions from:

(require math/number-theory)

2^256

(next-prime 2^256)

 

{{out}}

Build a lazy infinite list of primes using the Raku 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.

 

 

say "The first twenty primes:\n ", "[{@primes[^20].fmt("%d", ', ')}]";

sub between (@p, $l, $u) {

gather for @p { .take if $l < $_ < $u; last if $_ >= $u }

{{out}}

<pre>The first twenty primes:

The 10,000th prime:

104729</pre>

 

=={{header|REXX}}==

 

This REXX program uses some hardcoded divisions. &nbsp; While the hardcoded divisions are not necessary, they do speed up the division process in validating if a number is prime (or not), &nbsp; and the hardcoded divisions bypass the repetitive tests to see if a (low) prime that is being used for division is greater than the number being divided (tested). &nbsp; The hardcoded divisions also bypass (or, at least, postpones) the computation of the integer square roots.

parse arg f .; if f=='' then f= 20 /*allow specifying number for 1 ──► F.*/

_i= ' (inclusive) '; _b= 'between '; _tnp= 'the number of primes' _b; _tn= 'the primes'

L= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103

do #=1 for words(L); p= word(L, #); @.#= p; !.p=1; end /*#*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

see "first twenty primes : "

i = 1

next

return true

Output:

<pre>

=={{header|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.

 

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

{{out}}

<pre>

Uses the code from [[Sieve_of_Eratosthenes#Unbounded_Page-Segmented_bit-packed_odds-only_version_with_Iterator]]; copy that code into a file named <code>src/pagesieve.rs</code> and prepend <code>pub</code> to all function declarations used in this code (<code>count_primes_paged</code> and <code>primes_paged</code>).

 

 

use pagesieve::{count_primes_paged, primes_paged};

// rust enumerations are zero base, so need to subtract 1!!!

println!("The 10,000th prime is {}", primes_paged().nth(10_000 - 1).unwrap());

{{out}}

<pre>

cannot be used, because it needs a limit. Instead the function getPrime is used.

GetPrime generates all primes in sequence.

 

const func boolean: isPrime (in integer: number) is func

until primeNum = 9999; # discard up to and including the 9,999 prime!

writeln("The 10,000th prime: " <& getPrime);

 

{{out}}

 

=={{header|Sidef}}==

say ("Between 100 and 150: ", primes(100,150).join(' '))

say (prime_count(7700,8000), " primes between 7700 and 8000")

{{out}}

<pre>

 

The [[Sieve_of_Eratosthenes#Unbounded_.28Odds-Only.29_Versions]] Swift examples contain several versions that are Extensible Prime Generators using the Sieve of Eratosthenese. One of the simplest is the Hashed Dictionary, reproduced here as follows:

 

func soeDictOdds() -> UnfoldSequence<Int, Int> {

 

print(answr)

{{output}}

<pre>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

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

# An iterative version of the Sieve of Eratosthenes.

}

puts prime10000=$prime

{{out}}

<pre>

 

=={{header|VBA}}==

 

Sub Main()

ReDim Preserve L(c)

ListPrimes = L

{{out}}

<pre>For N = 133 218 295, execution time : 9,422 s, 7 550 284 primes numbers.

The last prime I could find is the : 7 550 283th, Value : 133 218 289</pre>

 

=={{header|Wren}}==

This uses a larger wheel than the sieve in the Wren-math module and is a bit faster if one is sieving beyond about 10^7.

 

var primeSieve = Fn.new { |limit|

Fmt.print("\nThe 10,000th prime is: $,d", primes[9999])

Fmt.print("\nThe 100,000th prime is: $,d", primes[99999])

 

{{out}}

 

Implementation:

const std = @import("std");

const builtin = std.builtin;

};

}

Driver code:

const std = @import("std");

const sieve = @import("sieve.zig");

const heap = std.heap;

 

pub fn main() !void {

try part1();

try stdout.print("There are {} primes between 7700 and 8000.\n", .{count});

}

// exercize 3: find big primes

fn part3() !void {

}

}

{{Out}}

<pre>

 

=={{header|zkl}}==

 

fcn postponed_sieve(){ # postponed sieve, by Will Ness

while(D.holds(x)){ x += s } # increment by the given step

D[x] = s;

primes.walk(20).println(); // first 20 primes

 

// or to carry on until the 100,000th:

{{out}}

<pre>

Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), this is a direct drop in for the above:

{{libheader|GMP}}

For example:

{{out}}

<pre>