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)

10001th prime

From Rosetta Code
10001th prime 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


Find and show on this page the 10001st prime number.

ALGOL 68[edit]

Chebyshev showed that the limit of pi( n ) / ( n / ln(n) ) as n approaches infinity is 1 ( pi( n ) is the number of primes up to n ).
The APPROXIMATESIEVESIZEFOR operator uses this to find a rough value for size of sieve needed to contain the required number of primes.

BEGIN # find the 10001st prime #
PR read "primes.incl.a68" PR
# construct a sieve of primes that should be large enough to contain 10001 primes #
INT required prime = 10 001;
[]BOOL prime = PRIMESIEVE APPROXIMATESIEVESIZEFOR required prime;
INT p count := 1;
FOR n FROM 3 BY 2 WHILE p count < required prime DO
IF prime[ n ] THEN
p count +:= 1;
IF p count = required prime THEN
print( ( "Prime ", whole( required prime, 0 ), " is ", whole( n, 0 ) ) )
FI
FI
OD
END
Output:
Prime 10001 is 104743

Arturo[edit]

primes: select 2..110000 => prime?
print primes\[10000]
Output:
104743

AWK[edit]

 
# syntax: GAWK -f 10001TH_PRIME.AWK
# converted from FreeBASIC
BEGIN {
printf("%s\n",main(10001))
exit(0)
}
function main(n, p,pn) {
if (n == 1) { return(2) }
p = 3
pn = 1
while (pn < n) {
if (is_prime(p)) {
pn++
}
p += 2
}
return(p-2)
}
function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (n % 2 == 0) { return(n == 2) }
if (n % 3 == 0) { return(n == 3) }
while (d*d <= n) {
if (n % d == 0) { return(0) }
d += 2
if (n % d == 0) { return(0) }
d += 4
}
return(1)
}
 
Output:
104743

BASIC[edit]

BASIC256[edit]

function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
 
function prime(n)
if n=1 then return 2
p = 3
pn = 1
while pn < n
if isPrime(p) then pn += 1
p += 2
end while
return p-2
end function
 
print prime(10001)
end

PureBasic[edit]

Procedure isPrime(v.i)
If v <= 1  : ProcedureReturn #False
ElseIf v < 4  : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9  : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
 
Procedure prime(n.i)
If n = 1
ProcedureReturn 2
EndIf
p.i = 3
pn.i = 1
While pn < n
If isprime(p)
pn + 1
EndIf
p + 2
Wend
ProcedureReturn p-2
EndProcedure
 
OpenConsole()
n = prime(10001)
PrintN(Str(n))
CloseConsole()

Yabasic[edit]

sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
 
sub prime(n)
if n = 1 then return 2 : fi
p = 3
pn = 1
while pn<n
if isPrime(p) then pn = pn + 1 : fi
p = p + 2
wend
return p-2
end sub
 
print prime(10001)
end


C[edit]

#include<stdio.h>
#include<stdlib.h>
 
int isprime( int p ) {
int i;
if(p==2) return 1;
if(!(p%2)) return 0;
for(i=3; i*i<=p; i+=2) {
if(!(p%i)) return 0;
}
return 1;
}
 
int prime( int n ) {
int p, pn=1;
if(n==1) return 2;
for(p=3;pn<n;p+=2) {
if(isprime(p)) pn++;
}
return p-2;
}
 
int main(void) {
printf( "%d\n", prime(10001) );
return 0;
}
Output:
104743

C#[edit]

Comparing performance of the one-at-a-time method vs the sieve of Eratosthenes method. About ten times faster for the sieve. It may appear that the sieve may be off by one, pr[10000] but since the array is zero based, it's the 10001st value.

using System; class Program {
 
static bool isprime(uint p ) { if ((p & 1) == 0) return p == 2;
if ((p % 3) == 0) return p == 3;
for (uint i = 5, d = 4; i * i <= p; i += (d = 6 - d))
if (p % i == 0) return false; return true; }
 
static uint prime(uint n) { uint p, d, pn;
for (p = 5, d = 4, pn = 2; pn < n; p += (d = 6 - d))
if (isprime(p)) pn++; return p - d; }
 
static void Main(string[] args) {
Console.WriteLine("One-at-a-time vs sieve of Eratosthenes");
var sw = System.Diagnostics.Stopwatch.StartNew();
var t = prime(10001); sw.Stop(); double e1, e2;
Console.Write("{0:n0} {1} ms", prime(10001),
e1 = sw.Elapsed.TotalMilliseconds);
sw.Restart(); uint n = 105000, i, j; var pr = new uint[10100];
pr[0] = 2; pr[1] = 3; uint pc = 2, r, d, ii;
var pl = new bool[n + 1]; r = (uint)Math.Sqrt(n);
for (i = 9; i < n; i += 6) pl[i] = true;
for (i = 5, d = 4; i <= r; i += (d = 6 - d)) if (!pl[i]) {
pr[pc++] = i; for (j = i * i, ii = i << 1; j <= n; j += ii)
pl[j] = true; }
for ( ;i <= n; i += (d = 6 - d)) if (!pl[i]) pr[pc++] = i;
t = pr[10000]; sw.Stop();
Console.Write(" {0:n0} {1} μs {2:0.000} times faster", t,
(e2 = sw.Elapsed.TotalMilliseconds) * 1000.0, e1 / e2); } }
Output @ Tio.run:
One-at-a-time vs sieve of Eratosthenes
104,743 3.8943 ms  104,743 357.9 μs  10.881 times faster

C++[edit]

Library: Primesieve
#include <iostream>
#include <locale>
 
#include <primesieve.hpp>
 
int main() {
std::cout.imbue(std::locale(""));
std::cout << "The 10,001st prime is " << primesieve::nth_prime(10001) << ".\n";
}
Output:
The 10,001st prime is 104,743.

F#[edit]

This task uses Extensible Prime Generator (F#)

 
// 10001st prime. Nigel Galloway: November 22nd., 2021
printfn $"%d{Seq.item 10000 (primes32())}"
 
Output:
104743

Factor[edit]

USING: math math.primes prettyprint ;
 
2 10,000 [ next-prime ] times .
Output:
104743

Fermat[edit]

 
Prime(10001);
 
Output:
104743

FreeBASIC[edit]

 
#include "isprime.bas"
function prime( n as uinteger ) as ulongint
if n=1 then return 2
dim as integer p=3, pn=1
while pn<n
if isprime(p) then pn + = 1
p += 2
wend
return p-2
end function
 
print prime(10001)
 
Output:
104743

Frink[edit]

nth[primes[], 10001-1]
Output:
104743


GW-BASIC[edit]

10 PN=1
20 P = 3
30 WHILE PN < 10001
40 GOSUB 100
50 IF Q = 1 THEN PN = PN + 1
60 P = P + 2
70 WEND
80 PRINT P-2
90 END
100 REM tests if a number is prime
110 Q=0
120 IF P = 2 THEN Q = 1: RETURN
130 IF P=3 THEN Q=1:RETURN
140 I=1
150 I=I+2
160 IF INT(P/I)*I = P THEN RETURN
170 IF I*I<=P THEN GOTO 150
180 Q = 1
190 RETURN
Output:
104743

Go[edit]

package main
 
import "fmt"
 
func isPrime(n int) bool {
if n == 1 {
return false
}
i := 2
for i*i <= n {
if n%i == 0 {
return false
}
i++
}
return true
}
 
func main() {
var final, pNum int
 
for i := 1; pNum < 10001; i++ {
if isPrime(i) {
pNum++
}
final = i
}
fmt.Println(final)
}
 
Output:
104743

J[edit]

p:10000      NB. the index starts at 0; p:0 = 2
Output:
104743

Java[edit]

Uses the PrimeGenerator class from Extensible prime generator#Java.

public class NthPrime {
public static void main(String[] args) {
System.out.printf("The 10,001st prime is %,d.\n", nthPrime(10001));
}
 
private static int nthPrime(int n) {
assert n > 0;
PrimeGenerator primeGen = new PrimeGenerator(10000, 100000);
int prime = primeGen.nextPrime();
while (--n > 0)
prime = primeGen.nextPrime();
return prime;
}
}
Output:
The 10,001st prime is 104,743.

jq[edit]

Works with: jq

Works with gojq, the Go implementation of jq

A solution without any pre-determined numbers or guesses.

See Erdős-primes#jq for a suitable definition of `is_prime` as used here.

# Output: a stream of the primes
def primes: 2, (range(3; infinite; 2) | select(is_prime));
 
# The task
# jq uses an index-origin of 1 and so:
nth(10000; primes)
Output:
104743

Julia[edit]

julia> using Primes
 
julia> prime(10001)
104743
 

Mathematica / Wolfram Language[edit]

Prime[10001]
Output:

104743

PARI/GP[edit]

prime(10001)
Output:
%1 = 104743

Perl[edit]

Library: ntheory
use strict;
use warnings;
use feature 'say';
 
# the lengthy wait increases the delight in finally seeing the answer
my($n,$c) = (1,0);
while () {
$c++ if (1 x ++$n) !~ /^(11+)\1+$/;
$c == 10_001 and say $n and last;
}
 
# or if for some reason you want the answer quickly
use ntheory 'nth_prime';
say nth_prime(10_001);
Output:
104743
104743

Phix[edit]

with js ?get_prime(10001)
Output:
104743


Picat[edit]

go ?=>
println(nth_prime(10001)),
 
 % faster but probably considered cheating
nth(10001,primes(200000),P),
println(P).
 
nth_prime(Choosen) = P =>
nth_prime(1,0,Choosen, P).
 
nth_prime(Num, Choosen, Choosen, Num) :-
prime(Num).
nth_prime(Num, Ix, Choosen, P) :-
Ix < Choosen,
next_prime(Num, P2),
nth_prime(P2, Ix+1, Choosen, P).
 
next_prime(Num, P) :-
next_prime2(Num+1, P).
next_prime2(Num, Num) :-
prime(Num).
next_prime2(Num, P) :-
next_prime2(Num+1,P).
Output:
104743
104743

Python[edit]

#!/usr/bin/python
 
def isPrime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
 
def prime(n: int) -> int:
if n == 1:
return 2
p = 3
pn = 1
while pn < n:
if isPrime(p):
pn += 1
p += 2
return p-2
 
if __name__ == '__main__':
print(prime(10001))
Output:
104743

Racket[edit]

#lang racket
(require math/number-theory)
; Index starts at 0, (nth-prime 0) is 2
(nth-prime 10000)
Output:
104743

Raku[edit]

say (^).grep( &is-prime )[10000]
Output:
104743

REXX[edit]

/* REXX */
Parse Version v
Say v
Call Time 'R'
z=1
p.0=3
p.1=2
p.2=3
p.3=5
Do n=5 By 2 Until z=10001
If right(n,1)=5 Then Iterate
Do i=2 To p.0 Until b**2>n
b=p.i
If n//b=0 Then Leave
End
If b**2>n Then Do
z=p.0+1
p.z=n
p.0=z
End
End
Say z n time('E')
Output:
H:\>rexx prime10001
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 8 Sep 2020
10001 104743 0.219000

H:\>regina prime10001
REXX-Regina_3.9.4(MT) 5.00 25 Oct 2021
10001 104743 .615000

Ring[edit]

 
load "stdlib.ring"
see "working..." + nl
num = 0 pr = 0 limit = 10001
 
while true
num++
if isprime(num) pr++ ok
if pr = limit exit ok
end
 
see "" + num + nl + "done..." + nl
 
Output:
working...
The 10001th prime is: 104743
done...

Ruby[edit]

require "prime"
puts Prime.lazy.drop(10_000).next
Output:
104743

Rust[edit]

// [dependencies]
// primal = "0.3"
 
fn main() {
let p = primal::StreamingSieve::nth_prime(10001);
println!("The 10001st prime is {}.", p);
}
Output:
The 10001st prime is 104743.

Sidef[edit]

say 10001.prime
Output:
104743

Wren[edit]

Library: Wren-math
Library: Wren-fmt
import "./math" for Int
import "./fmt" for Fmt
 
var n = 10001
var limit = (n.log * n * 1.2).floor // should be enough
var primes = Int.primeSieve(limit)
Fmt.print("The $,r prime is $,d.", n, primes[n-1])
Output:
The 10,001st prime is 104,743.

XPL0[edit]

func IsPrime(N); \Return 'true' if odd N > 2 is prime
int N, I;
[for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
 
int C, N;
[C:= 1; \count 2 as first prime
N:= 3;
loop [if IsPrime(N) then
[C:= C+1;
if C = 10001 then quit;
];
N:= N+2;
];
IntOut(0, N);
]
Output:
104743