10001th prime

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

Task

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

C

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

}</lang>

Output:

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

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:

Factor

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

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

Output:

Fermat

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

Output:

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

Output:

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:

J

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

Output:

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

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

Output:

104743
104743

Phix

with js ?get_prime(10001)

Output:

Raku

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

Output:

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

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.