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

<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

Arturo

<lang rebol>primes: select 2..110000 => prime? print primes\[10000]</lang>

Output:

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

BASIC

BASIC256

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

PureBasic

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

Yabasic

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

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:

One-at-a-time vs sieve of Eratosthenes
104,743 3.8943 ms  104,743 357.9 μs  10.881 times faster

C#

<lang csharp>using System; using System.Text; // PRIME russian DANILIN namespace p10001 // 1 second 10001 104743 { class Program // rextester.com/YXNR89875

   { static void Main(string[] args)
       { int max=10001; int n=1; int p=1; int f; int j; 
           while (n <= max) 
           { f=0; j=2;
               while (f < 1) 
               { if (j >= Convert.ToInt32(Math.Pow(p,0.5))) 
                   { 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(); 

}}}</lang>

Output:

104743

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

Frink

<lang frink>nth[primes[], 10001-1]</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

Go

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

} </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));

1. The task
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>

Mathematica / Wolfram Language

<lang Mathematica>Prime[10001]</lang>

Output:

104743

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

Picat

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

Output:

104743
104743

Python

<lang python>#!/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))</lang>

Output:

104743

Python

<lang python>import time; max=10001; n=1; p=1; # PRIMES russian DANILIN while n<=max: # 10001 104743 5 seconds

   f=0; j=2 # rextester.com/AHEH3087
   while f < 1:
       if j >= int(p**0.5):
           f=2
       if p % j == 0:
           f=1
       j+=1
   if f != 1:
       n+=1;
       #print(n,p);            
   p+=2

print(n-1,p-2) print(time.perf_counter())</lang>

Output:

10001 104743 7 seconds

QB64

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

Output:

10001 104743 0.35 seconds

QB64

<lang QB64>'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</lang>

Output:

10001 104743 0.11 seconds

R

<lang R>library(primes) nth_prime(10001)</lang>

Output:

104743

Racket

<lang Racket>#lang racket (require math/number-theory)

Index starts at 0, (nth-prime 0) is 2

(nth-prime 10000)</lang>

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

Ruby

<lang ruby>require "prime" puts Prime.lazy.drop(10_000).next</lang>

Output:

104743

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.

Sidef

<lang ruby>say 10001.prime</lang>

Output:

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