I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Piprimes

From Rosetta Code
Piprimes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

pi(n), the number of primes <= n, where pi(n) < 22


Also see



ALGOL 68[edit]

BEGIN # Show some values of pi(n) - the number of priems <= n  #
# reurns a sieve of primes up to n #
PROC prime sieve = ( INT n )[]BOOL:
BEGIN
[ 1 : n ]BOOL p;
p[ 1 ] := FALSE; p[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI
OD;
p
END # prime sieve # ;
# show pi(n) for n up to 21 #
INT max number = 100; # guess of how large the primes we need are #
INT max pi = 21;
[]BOOL prime = prime sieve( max number );
INT pi := 0;
FOR i TO max number
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
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[edit]

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]
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[edit]

 
# 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)
}
 
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[edit]

FreeBASIC[edit]

#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
 
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[edit]

    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

C[edit]

#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;
}
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[edit]

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();
 
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#[edit]

 
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
// 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 "")
 
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[edit]

Works with: Factor version 0.99 2021-02-05
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
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[edit]

n:=0; p:=0
while n<22 do !n;!' ';p:=p+1;if Isprime(p)=1 then n:=n+1; fi; od
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[edit]

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
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[edit]

}[email protected](>:@i.&.p:) 21
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[edit]

Translation of: Wren
Library: Go-rcu
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))
}
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.

Julia[edit]

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)
 
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[edit]

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


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[edit]

n=0; p=0
while(n<22, print(n); if(isprime(p),n=n+1);p=p+1)

Perl[edit]

Library: ntheory
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;
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[edit]

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[edit]

my @pi = (1..*).map: { state $pi = 0; $pi += .is-prime };
 
say @pi[^(@pi.first: * >= 22, :k)].batch(10)».fmt('%2d').join: "\n";
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[edit]

/*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 [email protected].#+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
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[edit]

 
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
 
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[edit]

1..(prime(22)-1) -> map { .prime_count }.say
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[edit]

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt
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).")
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[edit]

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