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 reuired 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
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:
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>
- 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
Julia
<lang julia>julia> using Primes
julia> prime(10001) 104743 </lang>
PARI/GP
<lang parigp>prime(10001)</lang>
- Output:
%1 = 104743
Perl
<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:
104743
Raku
<lang perl6>say (^∞).grep( &is-prime )[10000]</lang>
- Output:
104743
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
<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.