# 10001th prime

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.

## ALGOL 68

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.

<lang algol68>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</lang>

Output:
```Prime 10001 is 104743
```

## AWK

<lang AWK>

1. syntax: GAWK -f 10001TH_PRIME.AWK
2. 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)
```

} </lang>

Output:
```104743
```

## C

<lang c>#include<stdio.h>

1. 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;
```

}</lang>

Output:
`104743`

## C#

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. <lang csharp>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); } }</lang>
```
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++

Library: Primesieve

<lang cpp>#include <iostream>

1. include <locale>
1. include <primesieve.hpp>

int main() {

```   std::cout.imbue(std::locale(""));
std::cout << "The 10,001st prime is " << primesieve::nth_prime(10001) << ".\n";
```

}</lang>

Output:
```The 10,001st prime is 104,743.
```

## F#

This task uses Extensible Prime Generator (F#) <lang fsharp> // 10001st prime. Nigel Galloway: November 22nd., 2021 printfn \$"%d{Seq.item 10000 (primes32())}" </lang>

Output:
```104743
```

## Factor

<lang factor>USING: math math.primes prettyprint ;

2 10,000 [ next-prime ] times .</lang>

Output:
```104743
```

## Fermat

<lang fermat> Prime(10001); </lang>

Output:
`104743`

## FreeBASIC

<lang freebasic>

1. 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) </lang>

Output:
`104743`

## GW-BASIC

<lang gwbasic>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</lang>

Output:
`104743`

## J

<lang j>p:10000 NB. the index starts at 0; p:0 = 2</lang>

Output:
`104743`

## Java

Uses the PrimeGenerator class from Extensible prime generator#Java. <lang 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;
}
```

}</lang>

Output:
```The 10,001st prime is 104,743.
```

## jq

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. <lang jq># Output: a stream of the primes def primes: 2, (range(3; infinite; 2) | select(is_prime));

2. jq uses an index-origin of 1 and so:

nth(10000; primes)</lang>

Output:
```104743
```

## Julia

<lang julia>julia> using Primes

julia> prime(10001) 104743 </lang>

## PARI/GP

<lang parigp>prime(10001)</lang>

Output:
`%1 = 104743`

## Perl

Library: ntheory

<lang perl>use strict; use warnings; use feature 'say';

1. 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;
```

}

1. or if for some reason you want the answer quickly

use ntheory 'nth_prime'; say nth_prime(10_001);</lang>

Output:
```104743
104743```

## Phix

```with js ?get_prime(10001)
```
Output:
```104743
```

## Raku

<lang perl6>say (^∞).grep( &is-prime )[10000]</lang>

Output:
`104743`

## REXX

<lang rexx>/* 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')</lang>

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

<lang ring> 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 </lang>

Output:
```working...
The 10001th prime is: 104743
done...
```

## Rust

<lang rust>// [dependencies] // primal = "0.3"

fn main() {

```   let p = primal::StreamingSieve::nth_prime(10001);
println!("The 10001st prime is {}.", p);
```

}</lang>

Output:
```The 10001st prime is 104743.
```

## Wren

Library: Wren-math
Library: Wren-fmt

<lang ecmascript>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])</lang>

Output:
```The 10,001st prime is 104,743.
```

## XPL0

<lang XPL0>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); ]</lang>

Output:
```104743
```