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.

Task

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.

Library: ALGOL 68-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

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

Output:

104743

AWK

# 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

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

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

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

#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 DANILIN
namespace 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., 2021
printfn $"%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-2
end function

print prime(10001)

Output:

104743

Frink

nth[primes[], 10001-1]

Output:

104743

GW-BASIC

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

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

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

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+=1
print(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 DANILIN
While 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+1
Wend
Print 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  .109375
max = 10001: n=1: p=0: t = Timer ' PRIMES.bas
While 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+1
Wend
Print 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 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

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

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

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