Piprimes
- Task
pi(n), the number of primes <= n, where pi(n) < 22
- Also see
-
- Prime-counting_function.
- Tables and hints by Tomás Oliveira e Silva.
- the OEIS entry: A0000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n)....
Action!
<lang Action!>INCLUDE "H6:SIEVE.ACT"
PROC Main()
DEFINE MAX="100" BYTE ARRAY primes(MAX+1) INT n=[0],p=[1]
Put(125) PutE() ;clear the screen Sieve(primes,MAX+1) WHILE n<22 DO PrintB(n) Put(32) p==+1 IF primes(p) THEN n==+1 FI OD
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
ALGOL 68
<lang algol68>BEGIN # Show some values of pi(n) - the number of priems <= n #
# show pi(n) for n up to 21 # INT max prime = 100; # guess of how large the primes we need are # INT max pi = 21; PR read "primes.incl.a68" PR []BOOL prime = PRIMESIEVE max prime; INT pi := 0; FOR i TO UPB prime WHILE IF prime[ i ] THEN pi +:= 1 FI; pi <= max pi DO print( ( " ", whole( pi, -2 ) ) ); IF i MOD 10 = 0 THEN print( ( newline ) ) FI OD
END</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Arturo
<lang rebol>primes: select 2..1000 => prime? piprimes: function [n] -> size select primes 'z [z =< n]
loop split.every: 10 select map 1..100 => piprimes => [& < 22] 'a ->
print map a => [pad to :string & 3]</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
AWK
<lang AWK>
- syntax: GAWK -f PIPRIMES.AWK
- converted from FreeBASIC
BEGIN {
while (1) { if (is_prime(++curr)) { running++ } if (running == 22) { break } printf("%3d%1s",running,++count%10?"":"\n") } printf("\nPiPrimes 1-%d: %d\n",running-1,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21 PiPrimes 1-21: 78
BASIC
FreeBASIC
<lang freebasic>#define UPTO 22
- include "isprime.bas"
dim as integer running = 0, curr=0 do
curr += 1 if isprime(curr) then running += 1 if running = UPTO then exit do print running;" ";
loop print : end </lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Tiny BASIC
<lang tinybasic> LET N = 0
LET P = 0 10 IF N = 22 THEN END PRINT N LET P = P + 1 GOSUB 100 20 IF Z = 1 THEN LET N = N + 1 GOTO 10
100 REM PRIMALITY BY TRIAL DIVISION
LET Z = 1 LET I = 2
110 IF (P/I)*I = P THEN LET Z = 0
IF Z = 0 THEN RETURN LET I = I + 1 IF I*I <= P THEN GOTO 110 RETURN</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
int isprime( int n ) { int i;
if (n<2) return 0;
for(i=2; i*i<=n; i++) { if (n % i == 0) {return 0;} } return 1; }
int main(void) { int n = 0, p = 1; while (n<22) { printf( "%d ", n ); p++; if (isprime(p)) n+=1;
}
return 0; }</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Cowgol
<lang cowgol>include "cowgol.coh";
sub isPrime(n: uint8): (r: uint8) is
var i: uint8 := 2; r := 0; if n>=2 then while i*i <= n loop if n%i == 0 then return; end if; i := i + 1; end loop; r := 1; end if;
end sub;
var count: uint8 := 0; var n: uint8 := 1; const MAX := 22;
while count < MAX loop
print_i8(count); print_char('\t'); n := n + 1; count := count + isPrime(n); if n % 10 == 1 then print_nl(); end if;
end loop; print_nl(); </lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // PiPrimes: Nigel Galloway. April 5th., 2021 let fN=let i=primes32() in Seq.unfold(fun(n,g,l)->Some(l,if n=g then (n+1,Seq.head i,l+1) else (n+1,g,l)))(1,Seq.head i,0) fN|>Seq.takeWhile((>)22)|>Seq.chunkBySize 20|>Seq.iter(fun n->Array.iter(printf "%2d ") n; printfn "") </lang>
- Output:
0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Factor
<lang factor>USING: formatting grouping io lists math.primes math.primes.lists math.ranges math.statistics sequences ;
21 lprimes lnth [1,b) [ prime? ] cum-count 10 group [ [ "%2d " printf ] each nl ] each</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Fermat
<lang fermat>n:=0; p:=0 while n<22 do !n;!' ';p:=p+1;if Isprime(p)=1 then n:=n+1; fi; od</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
FOCAL
<lang FOCAL>01.10 S C=0 01.20 S N=1 01.30 T %3,C 01.40 S N=N+1 01.50 D 2;S C=C+A 01.60 I (C-22)1.3 01.70 T ! 01.80 Q
02.10 S I=1 02.20 S I=I+1 02.30 I (I*I-N-1)2.4;S A=1;R 02.40 S A=N/I 02.50 I (FITR(A)-A)2.2;S A=0</lang>
- Output:
= 0= 1= 2= 2= 3= 3= 4= 4= 4= 4= 5= 5= 6= 6= 6= 6 = 7= 7= 8= 8= 8= 8= 9= 9= 9= 9= 9= 9= 10= 10= 11= 11 = 11= 11= 11= 11= 12= 12= 12= 12= 13= 13= 14= 14= 14= 14= 15= 15 = 15= 15= 15= 15= 16= 16= 16= 16= 16= 16= 17= 17= 18= 18= 18= 18 = 18= 18= 19= 19= 19= 19= 20= 20= 21= 21= 21= 21= 21= 21
J
<lang J>}.@(>:@i.&.p:) 21</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
primes := rcu.Primes(79) // go up to the 22nd ix := 0 n := 1 count := 0 var pi []int for { if primes[ix] <= n { count++ if count == 22 { break } ix++ } n++ pi = append(pi, count) } fmt.Println("pi(n), the number of primes <= n, where n >= 1 and pi(n) < 22:") for i, n := range pi { fmt.Printf("%2d ", n) if (i+1)%10 == 0 { fmt.Println() } } fmt.Printf("\n\nHighest n for this range = %d.\n", len(pi))
}</lang>
- Output:
pi(n), the number of primes <= n, where n >= 1 and pi(n) < 22: 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21 Highest n for this range = 78.
jq
Works with gojq, the Go implementation of jq
This entry uses an approach based on streams of unbounded length; this has the advantage that no guessing or smarts is needed, either to provide a solution for the given bound (pi(n)<22) or any such bound.
For a suitable implementation of `is_prime` see e.g. Erdős-primes#jq.
Preliminaries <lang jq>def count(s): reduce s as $x (null; .+1);
def emit_until(cond; stream):
label $out | stream | if cond then break $out else . end;
def next_prime:
if . == 2 then 3 else first(range(.+2; infinite; 2) | select(is_prime)) end;</lang>
The task <lang jq># Generate pi($n) for $n > 0 def pi_primes:
foreach range(1; infinite) as $i ({n:0, np: 2}; # n counts, np is the next prime if $i < .np then . elif $i == .np then .n += 1 | .np |= next_prime else . end; .n);
emit_until(. >= 22; pi_primes)</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 ... 19 19 19 19 20 20 21 21 21 21 21 21
Julia
<lang julia>using Primes
function listpiprimes(maxpi)
pmask = primesmask(1, maxpi * maxpi) n = 0 for (i, isp) in enumerate(pmask) isp == 1 && (n += 1) >= maxpi && break print(rpad(n, 3), i % 10 == 0 ? "\n" : "") end
end
listpiprimes(22)
</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Nim
<lang Nim>import strutils
func isPrime(n: Natural): bool =
if n < 2: return false if n mod 2 == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 result = true
var pi = 0 var n = 1 while true:
stdout.write ($pi).align(2), if n mod 10 == 0: '\n' else: ' ' inc n if n.isPrime: inc pi if pi == 22: break
echo()</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
PARI/GP
<lang parigp>n = 1; while( primepi( n ) < 22,
printf( "%3d", primepi(n) ); if( n++ % 10 == 1, print()) )</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Perl
<lang perl>use strict; use warnings; use feature 'state'; use ntheory 'is_prime';
my @pi = map { state $pi = 0; $pi += is_prime $_ ? 1 : 0 } 1..1e4; do { print shift(@pi) . ' ' } until $pi[0] >= 22;</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Phix
with javascript_semantics integer ix = 1, n = 1, count = 0 sequence pi = {} while true do if get_prime(ix)<=n then count += 1 if count>=22 then exit end if ix += 1 end if n += 1 pi = append(pi,sprintf("%2d",count)) end while printf(1,"pi[1..%d]:\n%s\n",{length(pi),join_by(pi,1,10)})
- Output:
pi[1..78]: 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
Raku
<lang perl6>my @pi = (1..*).map: { state $pi = 0; $pi += .is-prime };
say @pi[^(@pi.first: * >= 22, :k)].batch(10)».fmt('%2d').join: "\n";</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21
REXX
<lang rexx>/*REXX program finds and displays pi(n) for 0 < N ≤ prime(22) {the 22nd prime is 87},*/ /*────────────────────────── where the pi function returns the number of primes ≤ N.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 22 /* " " " " " " */ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */ title= ' number of primes that are (for all N) ≤ prime(22) which is ' commas(@.hi) if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') idx= 1 /*initialize the index of output lines.*/ $=; pips= 0 /*a list of piPrimes numbers (so far). */
do j=1 for @.hi-1 /*gen list of piPrime numbers<prime(hi)*/ if !.j then pips= pips + 1 /*Is J prime? Then bump pips number.*/ if cols<0 then iterate /*Build the list (to be shown later)? */ c= commas(pips) /*maybe add commas to the number. */ $= $ right(c, max(w, length(c) ) ) /*add a Frobenius #──►list, allow big #*/ if j//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(j-1)", the" title /*display the foot separator for output*/ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 until #>hi /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above 3 lines saves time.*/ do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ number of primes that are (for all N) ≤ prime(22) which is 79 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 0 1 2 2 3 3 4 4 4 4 11 │ 5 5 6 6 6 6 7 7 8 8 21 │ 8 8 9 9 9 9 9 9 10 10 31 │ 11 11 11 11 11 11 12 12 12 12 41 │ 13 13 14 14 14 14 15 15 15 15 51 │ 15 15 16 16 16 16 16 16 17 17 61 │ 18 18 18 18 18 18 19 19 19 19 71 │ 20 20 21 21 21 21 21 21 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 78, the number of primes that are (for all N) ≤ prime(22) which is 79
Ring
<lang ring> load "stdlib.ring"
decimals(0) see "working..." + nl see "Piprimes are:" + nl
row = 0 limit1 = 400 Prim = []
for n = 1 to limit1
if isprime(n) add(Prim,n) ok
next
for n = 1 to len(Prim)
for m = 1 to len(Prim) if Prim[m] > n ind = m - 1 exit ok next row = row + 1 see "" + ind + " " if row%10 = 0 see nl ok
next
see nl + "Found " + row + " Piprimes." + nl see "done..." + nl </lang>
- Output:
working... Piprimes are: 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21 Found 78 Piprimes. done...
Sidef
<lang ruby>1..(prime(22)-1) -> map { .prime_count }.say</lang>
- Output:
[0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21]
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt
var primes = Int.primeSieve(79) // go up to the 22nd var ix = 0 var n = 1 var count = 0 var pi = [] while (true) {
if (primes[ix] <= n) { count = count + 1 if (count == 22) break ix = ix + 1 } n = n + 1 pi.add(count)
} System.print("pi(n), the number of primes <= n, where n >= 1 and pi(n) < 22:") for (chunk in Lst.chunks(pi, 10)) Fmt.print("$2d", chunk) System.print("\nHighest n for this range = %(pi.count).")</lang>
- Output:
pi(n), the number of primes <= n, where n >= 1 and pi(n) < 22: 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21 Highest n for this range = 78.
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
int Count, N, P; [Count:= 0; N:= 0; P:= 1; repeat if N<10 then ChOut(0, ^ );
IntOut(0, N); Count:= Count+1; if rem(Count/20) then ChOut(0, ^ ) else CrLf(0); P:= P+1; if IsPrime(P) then N:= N+1;
until N >= 22; ]</lang>
- Output:
0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 9 10 10 11 11 11 11 11 11 12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16 16 16 17 17 18 18 18 18 18 18 19 19 19 19 20 20 21 21 21 21 21 21