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

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.

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

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

`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    ODEND`
Output:
```Prime 10001 is 104743
```

## Arturo

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

## AWK

` # syntax: GAWK -f 10001TH_PRIME.AWK# converted from FreeBASICBEGIN {    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

### BASIC256

`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 Trueend 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-2end function print prime(10001)end`

### PureBasic

`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 #TrueEndProcedure 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-2EndProcedure OpenConsole()n = prime(10001)PrintN(Str(n))CloseConsole()`

### Yabasic

`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 Trueend 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-2end sub print prime(10001)end`

## C

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

### Sieve vs Trial Division

Comparing performance of the one-at-a-time trial division 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 trial division 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 trial division vs sieve of Eratosthenes
104,743 3.8943 ms  104,743 357.9 μs  10.881 times faster```

### Alternative Trial Division Method

`using System; using System.Text; // PRIME_numb.cs russian DANILINnamespace p10001 // 1 second  10001  104743 { class Program // rextester.com/ZBEPGE34760    { static void Main(string[] args)        { int max=10001; int n=1; int p=1; int f; int j; long s;            while (n <= max)             { f=0; j=2; s=Convert.ToInt32(Math.Pow(p,0.5));                while (f < 1)                 { if (j >= s)                     { f=2; }                   if (p % j == 0) { f=1; }                  j++;                }                if (f != 1) { n++; } // Console.WriteLine("{0} {1}", n, p);                p++;            }Console.Write("{0} {1}", n-1, p-1);Console.ReadKey(); }}}`
Output:
`104743`

## C++

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#

This task uses Extensible Prime Generator (F#)

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

## Factor

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

## Fermat

` Prime(10001); `
Output:
`104743`

## FreeBASIC

` #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-2end function print prime(10001) `
Output:
`104743`

## Frink

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

## GW-BASIC

`10 PN=120 P = 330 WHILE PN < 1000140 GOSUB 10050 IF Q = 1 THEN PN = PN + 160 P = P + 270 WEND80 PRINT P-290 END100 REM tests if a number is prime110 Q=0120 IF P = 2 THEN Q =  1: RETURN130 IF P=3 THEN Q=1:RETURN140 I=1150 I=I+2160 IF INT(P/I)*I = P THEN RETURN170 IF I*I<=P THEN GOTO 150180 Q = 1190 RETURN`
Output:
`104743`

## Go

`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

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

## Java

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

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

`julia> using Primes julia> prime(10001)104743 `

## Mathematica / Wolfram Language

`Prime[10001]`
Output:
```
104743

```

## PARI/GP

`prime(10001)`
Output:
`%1 = 104743`

## Perl

Library: ntheory
`use strict;use warnings;use feature 'say'; # the lengthy wait increases the delight in finally seeing the answermy(\$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 quicklyuse ntheory 'nth_prime';say nth_prime(10_001);`
Output:
```104743
104743```

## Phix

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

## Picat

`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

### Trial Division Method

`#!/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`

### Alternative Trial Division Method

`import time; max=10001; n=1; p=1; # PRIME_numb.py russian DANILIN while n<=max: # 78081 994271 45 seconds    f=0; j=2; s = int(p**0.5) # rextester.com/AAOHQ6342    while f < 1:        if j >= s:            f=2        if p % j == 0:            f=1        j+=1    if f != 1:        n+=1;        #print(n,p);    p+=1print(n-1,p-1)print(time.perf_counter())`
Output:
`10001 104743 7 seconds`

## QB64

### Trial Division Method

`max=10001: n=1: p=0: t=TIMER ' PRIMES.bas russian DANILINWHILE n <= max ' 10001 104743 0.35 seconds    f=0: j=2    WHILE f < 1        IF j >= p ^ 0.5 THEN f=2        IF p MOD j = 0 THEN f=1        j=j+1    WEND    IF f <> 1 THEN n=n+1: ' Print n, p    p=p+1WENDPRINT n-1, p-1, Timer-t`
Output:
`10001 104743 0.35 seconds`

### More Efficient TD Method

`'JRace's results:'Original version: 10001   104743  .21875'This version:     10001   104743  .109375max = 10001: n=1: p=0: t = TIMER ' PRIMES.basWHILE n <= max ' 10001 104743 0.35 seconds    f = 0: j = 2    pp = p^0.5 'NEW VAR: move exponentiation here, to outer loop    WHILE f < 1        ' If j >= p ^ 0.5 Then f=2 'original line        ' NOTE: p does not change in this loop,        '      therefore p^0.5 doesn't change;        '      moving p^0.5 to the outer loop will eliminate a lot of FP math)        IF j >= pp THEN f=2 'new version with exponentiation relocated        IF p MOD j = 0 THEN f=1        j=j+1    WEND    IF f <> 1 THEN n=n+1: ' Print n, p    p=p+1WENDPRINT n-1, p-1, TIMER - t`
Output:
`10001 104743 0.11 seconds`

## R

`library(primes)nth_prime(10001)`
Output:
`104743`

## Racket

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

## Raku

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

## REXX

`/* REXX */Parse Version vSay vCall Time 'R'z=1p.0=3p.1=2p.2=3p.3=5Do 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  EndSay 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

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

## Ruby

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

## Rust

`// [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

`say 10001.prime`
Output:
```104743
```

## Wren

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

## XPL0

`func IsPrime(N); \Return 'true' if odd N > 2 is primeint  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 primeN:= 3;loop    [if IsPrime(N) then            [C:= C+1;            if C = 10001 then quit;            ];        N:= N+2;        ];IntOut(0, N);]`
Output:
```104743
```