10001th prime: Difference between revisions
(Frink) |
m (typo) |
||
(70 intermediate revisions by 26 users not shown) | |||
Line 4: | Line 4: | ||
<br>Find and show on this page the 10001st prime number. |
<br>Find and show on this page the 10001st prime number. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
<syntaxhighlight lang="11l">V k = 10001 |
|||
V n = k * 17 |
|||
V primes = [1B] * n |
|||
primes[0] = primes[1] = 0B |
|||
L(i) 2 .. Int(sqrt(n)) |
|||
I !primes[i] |
|||
L.continue |
|||
L(j) (i * i .< n).step(i) |
|||
primes[j] = 0B |
|||
L(i) 0 .< n |
|||
I primes[i] |
|||
I k == 1 |
|||
print(i) |
|||
L.break |
|||
k--</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
104743 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 9: | Line 33: | ||
The APPROXIMATESIEVESIZEFOR operator uses this to find a rough value for size of sieve needed to contain the required number of primes. |
The APPROXIMATESIEVESIZEFOR operator uses this to find a rough value for size of sieve needed to contain the required number of primes. |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the 10001st prime # |
||
PR read "primes.incl.a68" PR |
PR read "primes.incl.a68" PR |
||
# construct a sieve of primes that should be large enough to contain 10001 primes # |
# construct a sieve of primes that should be large enough to contain 10001 primes # |
||
Line 23: | Line 47: | ||
FI |
FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 30: | Line 54: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
<syntaxhighlight lang="rebol">primes: select 2..110000 => prime? |
|||
print primes\[10000]</syntaxhighlight> |
|||
<lang rebol>primes: select 2..110000 => prime? |
|||
print primes\[10000]</lang> |
|||
{{out}} |
{{out}} |
||
Line 39: | Line 62: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
==== Converted from FreeBASIC ==== |
|||
<lang AWK> |
|||
<syntaxhighlight lang="awk"> |
|||
# syntax: GAWK -f 10001TH_PRIME.AWK |
# syntax: GAWK -f 10001TH_PRIME.AWK |
||
# converted from FreeBASIC |
|||
BEGIN { |
BEGIN { |
||
printf("%s\n",main(10001)) |
printf("%s\n",main(10001)) |
||
Line 71: | Line 95: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
==== Idiomatic ==== |
|||
<syntaxhighlight lang="awk"> |
|||
# awk -f 10001prime.awk |
|||
# n: odd number and n>8 |
|||
function IsOddPrime(n, i,limit) { |
|||
limit = int(sqrt(n)) |
|||
for (i=3;i <= limit;i+=2) |
|||
if (n%i==0) return 0 |
|||
return 1 |
|||
} |
|||
# pos: positive |
|||
function PrimePosition(pos, prime){ |
|||
pos -= ( (pos==1) ? prime=2 : prime=3 ) - 1 |
|||
while (pos) |
|||
if (IsOddPrime(prime+=2)) pos-- |
|||
return prime |
|||
} |
|||
BEGIN { print PrimePosition(10001) } |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 79: | Line 128: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|BASIC256}}=== |
==={{header|BASIC256}}=== |
||
< |
<syntaxhighlight lang="basic256">function isPrime(v) |
||
if v < 2 then return False |
if v < 2 then return False |
||
if v mod 2 = 0 then return v = 2 |
if v mod 2 = 0 then return v = 2 |
||
Line 102: | Line 151: | ||
print prime(10001) |
print prime(10001) |
||
end</ |
end</syntaxhighlight> |
||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|FreeBASIC}}=== |
|||
<syntaxhighlight 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) |
|||
</syntaxhighlight> |
|||
{{out}}<pre>104743</pre> |
|||
==={{header|Gambas}}=== |
|||
<syntaxhighlight lang="vbnet">'Use "isprime.bas" |
|||
Public Sub Main() |
|||
Print prime(10001) |
|||
End |
|||
Function prime(n As Integer) As Long |
|||
If n = 1 Then Return 2 |
|||
Dim p As Integer = 3, pn As Integer = 1 |
|||
While pn < n |
|||
If isPrime(p) Then pn += 1 |
|||
p += 2 |
|||
Wend |
|||
Return p - 2 |
|||
End Function </syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|BASICA}} |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}}<pre>104743</pre> |
|||
==={{header|PureBasic}}=== |
==={{header|PureBasic}}=== |
||
< |
<syntaxhighlight lang="purebasic">Procedure isPrime(v.i) |
||
If v <= 1 : ProcedureReturn #False |
If v <= 1 : ProcedureReturn #False |
||
ElseIf v < 4 : ProcedureReturn #True |
ElseIf v < 4 : ProcedureReturn #True |
||
Line 142: | Line 258: | ||
n = prime(10001) |
n = prime(10001) |
||
PrintN(Str(n)) |
PrintN(Str(n)) |
||
CloseConsole()</ |
CloseConsole()</syntaxhighlight> |
||
==={{header|QB64}}=== |
|||
====Trial Division Method==== |
|||
<syntaxhighlight lang="qbasic">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10001 104743 0.35 seconds</pre> |
|||
====More Efficient TD Method==== |
|||
<syntaxhighlight lang="qbasic">'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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10001 104743 0.11 seconds</pre> |
|||
==={{header|True BASIC}}=== |
|||
====Trial Division Method==== |
|||
{{trans|QB64}} |
|||
<syntaxhighlight lang="qbasic">LET max = 10001 |
|||
LET n = 1 |
|||
LET p = 0 |
|||
DO WHILE n <= max |
|||
LET f = 0 |
|||
LET j = 2 |
|||
DO WHILE f < 1 |
|||
IF j >= p^0.5 THEN LET f = 2 |
|||
IF REMAINDER(p, j) = 0 THEN LET f = 1 |
|||
LET j = j+1 |
|||
LOOP |
|||
IF f <> 1 THEN LET n = n+1 |
|||
LET p = p+1 |
|||
LOOP |
|||
PRINT p-1 |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
==={{header|Yabasic}}=== |
==={{header|Yabasic}}=== |
||
< |
<syntaxhighlight lang="yabasic">sub isPrime(v) |
||
if v < 2 then return False : fi |
if v < 2 then return False : fi |
||
if mod(v, 2) = 0 then return v = 2 : fi |
if mod(v, 2) = 0 then return v = 2 : fi |
||
Line 168: | Line 347: | ||
print prime(10001) |
print prime(10001) |
||
end</ |
end</syntaxhighlight> |
||
=={{header|bc}}== |
|||
<syntaxhighlight lang="bc">a[0] = 2 |
|||
a[o = 1] = 3 |
|||
for (n = 5; o < 10000; n += 2) { |
|||
for (i = 1; n % (p = a[i]) != 0; ++i) { |
|||
if (p * p > n) { |
|||
a[++o] = n |
|||
break |
|||
} |
|||
} |
|||
} |
|||
a[o]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include<stdio.h> |
||
#include<stdlib.h> |
#include<stdlib.h> |
||
Line 197: | Line 390: | ||
printf( "%d\n", prime(10001) ); |
printf( "%d\n", prime(10001) ); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}}<pre>104743</pre> |
{{out}}<pre>104743</pre> |
||
=={{header|C#|CSharp}}== |
=={{header|C#|CSharp}}== |
||
===Sieve vs Trial Division=== |
|||
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, <code>pr[10000]</code> but since the array is zero based, it's the 10001st value. |
|||
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, <code>pr[10000]</code> but since the array is zero based, it's the 10001st value. |
|||
<lang csharp>using System; class Program { |
|||
<syntaxhighlight lang="csharp">using System; class Program { |
|||
static bool isprime(uint p ) { if ((p & 1) == 0) return p == 2; |
static bool isprime(uint p ) { if ((p & 1) == 0) return p == 2; |
||
Line 214: | Line 408: | ||
static void Main(string[] args) { |
static void Main(string[] args) { |
||
Console.WriteLine("One-at-a-time vs sieve of Eratosthenes"); |
Console.WriteLine("One-at-a-time trial division vs sieve of Eratosthenes"); |
||
var sw = System.Diagnostics.Stopwatch.StartNew(); |
var sw = System.Diagnostics.Stopwatch.StartNew(); |
||
var t = prime(10001); sw.Stop(); double e1, e2; |
var t = prime(10001); sw.Stop(); double e1, e2; |
||
Line 229: | Line 423: | ||
t = pr[10000]; sw.Stop(); |
t = pr[10000]; sw.Stop(); |
||
Console.Write(" {0:n0} {1} μs {2:0.000} times faster", t, |
Console.Write(" {0:n0} {1} μs {2:0.000} times faster", t, |
||
(e2 = sw.Elapsed.TotalMilliseconds) * 1000.0, e1 / e2); } }</ |
(e2 = sw.Elapsed.TotalMilliseconds) * 1000.0, e1 / e2); } }</syntaxhighlight> |
||
{{out|Output @ Tio.run}} |
{{out|Output @ Tio.run}} |
||
<pre>One-at-a-time vs sieve of Eratosthenes |
<pre>One-at-a-time trial division vs sieve of Eratosthenes |
||
104,743 3.8943 ms 104,743 357.9 μs 10.881 times faster</pre> |
104,743 3.8943 ms 104,743 357.9 μs 10.881 times faster</pre> |
||
===Alternative Trial Division Method=== |
|||
<syntaxhighlight lang="csharp">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(); |
|||
}}}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|Primesieve}} |
{{libheader|Primesieve}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <locale> |
#include <locale> |
||
Line 244: | Line 461: | ||
std::cout.imbue(std::locale("")); |
std::cout.imbue(std::locale("")); |
||
std::cout << "The 10,001st prime is " << primesieve::nth_prime(10001) << ".\n"; |
std::cout << "The 10,001st prime is " << primesieve::nth_prime(10001) << ".\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 250: | Line 467: | ||
The 10,001st prime is 104,743. |
The 10,001st prime is 104,743. |
||
</pre> |
</pre> |
||
=={{header|Dart}}== |
|||
<syntaxhighlight lang="dart">import 'dart:math'; |
|||
bool isPrime(int n) { |
|||
if (n <= 1) return false; |
|||
if (n == 2) return true; |
|||
for (int i = 2; i <= sqrt(n); ++i) { |
|||
if (n % i == 0) return false; |
|||
} |
|||
return true; |
|||
} |
|||
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; |
|||
} |
|||
void main() { |
|||
print(prime(10001)); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|none}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IsPrime(N: integer): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: integer; |
|||
begin |
|||
if (N = 2) or (N=3) then Result:=true |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
else |
|||
begin |
|||
I:=5; |
|||
Stop:=Trunc(sqrt(N)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
Inc(I,6); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
end; |
|||
function Find10001thPrime: integer; |
|||
{Return the 10,001th prime number} |
|||
var Count: integer; |
|||
begin |
|||
Count:=1; |
|||
Result:= 3; |
|||
while true do |
|||
begin |
|||
if IsPrime(Result) then Count:= Count+1; |
|||
if Count=10001 then exit; |
|||
Inc(Result,2); |
|||
end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10,001th Prime= 104,743 |
|||
</pre> |
|||
=={{header|D}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="d"> |
|||
import std.stdio; |
|||
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 ) { |
|||
if(n==1) return 2; |
|||
int p, pn=1; |
|||
for(p=3;pn<n;p+=2) { |
|||
if(isprime(p)) pn++; |
|||
} |
|||
return p-2; |
|||
} |
|||
void main() |
|||
{ |
|||
writeln(prime(10_001)); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}}<pre>104743</pre> |
|||
=={{header|Erlang}}== |
|||
<syntaxhighlight lang="erlang"> |
|||
-module(task_10001th_prime). |
|||
-export([main/0]). |
|||
% 2 and 3 are both primes, so we start searching at 5 |
|||
main() -> search(5, 2, 2). |
|||
search(N, Inc, Count) when Count < 10_001 -> |
|||
case is_prime(N) of |
|||
true -> search(N + Inc, 6 - Inc, Count + 1); |
|||
false -> search(N + Inc, 6 - Inc, Count) |
|||
end; |
|||
search(N, Inc, _) -> N - 6 + Inc. |
|||
is_prime(P) -> is_prime(P, 5, 2). |
|||
is_prime(N, P, _) when P * P > N -> true; |
|||
is_prime(N, P, _) when N rem P =:= 0 -> false; |
|||
is_prime(N, P, Inc) -> is_prime(N, P + Inc, 6 - Inc). |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
timer:tc(task_10001th_prime, main, []). |
|||
{68615,104743} |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang="easylang"> |
|||
fastfunc isprim num . |
|||
if num mod 2 = 0 and num > 2 |
|||
return 0 |
|||
. |
|||
i = 3 |
|||
while i <= sqrt num |
|||
if num mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 2 |
|||
. |
|||
return 1 |
|||
. |
|||
i = 2 |
|||
repeat |
|||
if isprim i = 1 |
|||
nprim += 1 |
|||
. |
|||
until nprim = 10001 |
|||
i += 1 |
|||
. |
|||
print i |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// 10001st prime. Nigel Galloway: November 22nd., 2021 |
// 10001st prime. Nigel Galloway: November 22nd., 2021 |
||
printfn $"%d{Seq.item 10000 (primes32())}" |
printfn $"%d{Seq.item 10000 (primes32())}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 262: | Line 649: | ||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: math math.primes prettyprint ; |
||
2 10,000 [ next-prime ] times .</ |
2 10,000 [ next-prime ] times .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 271: | Line 658: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
<syntaxhighlight lang="pascal"> |
|||
<lang fermat> |
|||
Prime(10001); |
Prime(10001); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>104743</pre> |
|||
=={{header|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> |
|||
{{out}}<pre>104743</pre> |
{{out}}<pre>104743</pre> |
||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
< |
<syntaxhighlight lang="frink">nth[primes[], 10001-1]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 300: | Line 670: | ||
</pre> |
</pre> |
||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="futurebasic"> |
|||
local fn IsPrime( n as NSUInteger ) as BOOL |
|||
=={{header|GW-BASIC}}== |
|||
BOOL isPrime = YES |
|||
<lang gwbasic>10 PN=1 |
|||
NSUInteger i |
|||
20 P = 3 |
|||
30 WHILE PN < 10001 |
|||
if n < 2 then exit fn = NO |
|||
40 GOSUB 100 |
|||
if n = 2 then exit fn = YES |
|||
if n mod 2 == 0 then exit fn = NO |
|||
60 P = P + 2 |
|||
for i = 3 to int(n^.5) step 2 |
|||
70 WEND |
|||
if n mod i == 0 then exit fn = NO |
|||
80 PRINT P-2 |
|||
next |
|||
90 END |
|||
end fn = isPrime |
|||
100 REM tests if a number is prime |
|||
110 Q=0 |
|||
120 IF P = 2 THEN Q = 1: RETURN |
|||
local fn Prime( n as NSUInteger ) as long |
|||
130 IF P=3 THEN Q=1:RETURN |
|||
long p = 3, pn = 1 |
|||
140 I=1 |
|||
150 I=I+2 |
|||
if n = 1 then exit fn = 2 |
|||
160 IF INT(P/I)*I = P THEN RETURN |
|||
while ( pn < n ) |
|||
170 IF I*I<=P THEN GOTO 150 |
|||
if fn IsPrime( p ) then pn++ |
|||
180 Q = 1 |
|||
p += 2 |
|||
190 RETURN</lang> |
|||
wend |
|||
{{out}}<pre>104743</pre> |
|||
p -= 2 |
|||
end fn = p |
|||
print fn Prime(10001) |
|||
HandleEvents |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
104743 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 353: | Line 736: | ||
fmt.Println(final) |
fmt.Println(final) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>104743</pre> |
{{out}}<pre>104743</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">p:10000 NB. the index starts at 0; p:0 = 2</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743</pre> |
<pre>104743</pre> |
||
Line 363: | Line 746: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
Uses the PrimeGenerator class from [[Extensible prime generator#Java]]. |
Uses the PrimeGenerator class from [[Extensible prime generator#Java]]. |
||
< |
<syntaxhighlight lang="java">public class NthPrime { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
System.out.printf("The 10,001st prime is %,d.\n", nthPrime(10001)); |
System.out.printf("The 10,001st prime is %,d.\n", nthPrime(10001)); |
||
Line 376: | Line 759: | ||
return prime; |
return prime; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The 10,001st prime is 104,743. |
The 10,001st prime is 104,743. |
||
</pre> |
|||
=={{header|JavaScript}}== |
|||
Prime 10001 from Russia |
|||
jdoodle.com/h/2V1 |
|||
<syntaxhighlight lang="java"> |
|||
var max = 10001, n=1, p=1; var f,j,s |
|||
while (n <= max) |
|||
{ f=0; j=2; s = parseInt(Math.pow(p, 0.5)) |
|||
while (f < 1) |
|||
{ if (j >= s) f=2 |
|||
if ( p % j == 0 ) f=1 |
|||
j++ |
|||
} |
|||
if (f != 1) n++ // { document.write(n +" "+ p +"<br>") } |
|||
p++ |
|||
} |
|||
document.write("<br>"+ (n-1) +" "+ (p-1) +"<br>" ) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10001 104743 |
|||
</pre> |
</pre> |
||
Line 390: | Line 797: | ||
See [[Erdős-primes#jq]] for a suitable definition of `is_prime` as used here. |
See [[Erdős-primes#jq]] for a suitable definition of `is_prime` as used here. |
||
< |
<syntaxhighlight lang="jq"># Output: a stream of the primes |
||
def primes: 2, (range(3; infinite; 2) | select(is_prime)); |
def primes: 2, (range(3; infinite; 2) | select(is_prime)); |
||
# The task |
# The task |
||
# jq uses an index-origin of 1 and so: |
# jq uses an index-origin of 1 and so: |
||
nth(10000; primes)</ |
nth(10000; primes)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 402: | Line 809: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">julia> using Primes |
||
julia> prime(10001) |
julia> prime(10001) |
||
104743 |
104743 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
<lang |
<syntaxhighlight lang="mathematica">Prime[10001]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
104743 |
104743 |
||
</pre> |
</pre> |
||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima"> |
|||
primes_first_n(n) := ( |
|||
if n<=1 then |
|||
[] |
|||
else ( |
|||
L : [2], |
|||
for i:2 thru n do ( |
|||
L : append(L, [next_prime(last(L))]) |
|||
), |
|||
L |
|||
) |
|||
)$ |
|||
last(primes_first_n(10001)); |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
104743 |
|||
</pre> |
|||
=={{header|MiniScript}}== |
|||
<syntaxhighlight lang="miniscript"> |
|||
isPrime = function(n) |
|||
s = floor(n ^ 0.5) |
|||
for i in range(2, s) |
|||
if n % i == 0 then return false |
|||
end for |
|||
return true |
|||
end function |
|||
tt = time |
|||
c = 2 |
|||
p = 2 |
|||
lastPrime = 2 |
|||
while c < 10001 |
|||
p += 1 |
|||
if isPrime(p) then |
|||
c += 1 |
|||
end if |
|||
end while |
|||
print p |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
104743</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="Nim">func isPrime(n: Positive): bool = |
|||
## Return true if "n" is prime. |
|||
## Assume n >= 5 and n not multiple of 2 and 3. |
|||
var d = 5 |
|||
var step = 2 |
|||
while d * d <= n: |
|||
if n mod d == 0: |
|||
return false |
|||
inc d, step |
|||
step = 6 - step |
|||
result = true |
|||
iterator primes(): tuple[rank, value: int] = |
|||
## Yield the primes preceded by their rank in the sequence. |
|||
yield (1, 2) |
|||
yield (2, 3) |
|||
var idx = 2 |
|||
var n = 5 |
|||
var step = 2 |
|||
while true: |
|||
if n.isPrime: |
|||
inc idx |
|||
yield (idx, n) |
|||
inc n, step |
|||
step = 6 - step |
|||
for (i, n) in primes(): |
|||
if i == 10001: |
|||
echo "10001st prime: ", n |
|||
break |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10001st prime: 104743 |
|||
</pre> |
|||
=={{header|OCaml}}== |
|||
Using the function <code>seq_primes</code> from [[Extensible prime generator#OCaml]]: |
|||
<syntaxhighlight lang="ocaml">let () = |
|||
seq_primes |> Seq.drop 10000 |> Seq.take 1 |> Seq.iter (Printf.printf "%u\n")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
<lang |
<syntaxhighlight lang="parigp">prime(10001)</syntaxhighlight> |
||
{{out}}<pre>%1 = 104743</pre> |
{{out}}<pre>%1 = 104743</pre> |
||
=={{header|Pascal}}== |
|||
==={{header|Free Pascal}}=== |
|||
<syntaxhighlight lang="pascal"> |
|||
Program nth_prime; |
|||
Function nthprime(x : uint32): uint32; |
|||
Var primes : array Of uint32; |
|||
i,pr,count : uint32; |
|||
found : boolean; |
|||
Begin |
|||
setlength(primes, x); |
|||
primes[1] := 2; |
|||
count := 1; |
|||
i := 3; |
|||
Repeat |
|||
found := FALSE; |
|||
pr := 0; |
|||
Repeat |
|||
inc(pr); |
|||
found := i Mod primes[pr] = 0; |
|||
Until (primes[pr]*primes[pr] > i) Or found; |
|||
If Not found Then |
|||
Begin |
|||
inc(count); |
|||
primes[count] := i; |
|||
End; |
|||
inc(i,2); |
|||
Until count = x; |
|||
nthprime := primes[x]; |
|||
End; |
|||
Begin |
|||
writeln(nthprime(10001)); |
|||
End. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
104743 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 433: | Line 970: | ||
# or if for some reason you want the answer quickly |
# or if for some reason you want the answer quickly |
||
use ntheory 'nth_prime'; |
use ntheory 'nth_prime'; |
||
say nth_prime(10_001);</ |
say nth_prime(10_001);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743 |
<pre>104743 |
||
Line 439: | Line 976: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!-- |
<!--(phixonline)--> |
||
<syntaxhighlight lang="phix"> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">js</span> <span style="color: #0000FF;">?</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10001</span><span style="color: #0000FF;">)</span> |
|||
with js ?get_prime(10001) |
|||
<!--</lang>--> |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 447: | Line 985: | ||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
<syntaxhighlight 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).</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743 |
|||
104743</pre> |
|||
=={{header|Prolog}}== |
|||
for swi-prolog |
|||
<syntaxhighlight lang="prolog">isPrime(2). % prime generator |
|||
isPrime(N):- |
|||
between(3, inf, N), |
|||
N /\ 1 > 0, % odd |
|||
M is floor(sqrt(N)) - 1, % reverse 2*I+1 |
|||
Max is M div 2, |
|||
forall(between(1, Max, I), N mod (2*I+1) > 0). |
|||
do:- Index is 10001, |
|||
findnsols(Index, N, isPrime(N), PrimeList),!, |
|||
last(PrimeList, PrimeAtIndex), |
|||
format('prime(~d) is ~d', [Index, PrimeAtIndex]), nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>?- do. |
|||
prime(10001) is 104743 |
|||
true.</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Trial Division Method=== |
|||
<lang python>#!/usr/bin/python |
|||
<syntaxhighlight lang="python">#!/usr/bin/python |
|||
def isPrime(n): |
def isPrime(n): |
||
Line 469: | Line 1,054: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
print(prime(10001))</ |
print(prime(10001))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743</pre> |
<pre>104743</pre> |
||
===Alternative Trial Division Method=== |
|||
<syntaxhighlight lang="python">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())</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10001 104743 7 seconds</pre> |
|||
=={{header|Quackery}}== |
|||
The 10001st prime number is the 10000th odd prime number. |
|||
<code>prime</code> is defined at [[Miller–Rabin primality test#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> 1 10000 times [ 2 + dup prime until ] echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|R}}== |
|||
<syntaxhighlight lang="r">library(primes) |
|||
nth_prime(10001)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>104743</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require math/number-theory) |
(require math/number-theory) |
||
; Index starts at 0, (nth-prime 0) is 2 |
; Index starts at 0, (nth-prime 0) is 2 |
||
(nth-prime 10000)</ |
(nth-prime 10000)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743</pre> |
<pre>104743</pre> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>say (^∞).grep( &is-prime )[10000]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743</pre> |
<pre>104743</pre> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/* REXX */ |
||
Parse Version v |
Parse Version v |
||
Say v |
Say v |
||
Line 509: | Line 1,129: | ||
End |
End |
||
End |
End |
||
Say z n time('E')</ |
Say z n time('E')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>H:\>rexx prime10001 |
<pre>H:\>rexx prime10001 |
||
Line 520: | Line 1,140: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
Line 532: | Line 1,152: | ||
see "" + num + nl + "done..." + nl |
see "" + num + nl + "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 538: | Line 1,158: | ||
The 10001th prime is: 104743 |
The 10001th prime is: 104743 |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|HP|49}} |
|||
« 2 |
|||
1 10000 '''START''' NEXTPRIME '''NEXT''' |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre>1: 104743 |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
puts Prime.lazy.drop(10_000).next</ |
puts Prime.lazy.drop(10_000).next</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>104743 |
<pre>104743 |
||
</pre> |
</pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">// [dependencies] |
||
// primal = "0.3" |
// primal = "0.3" |
||
Line 553: | Line 1,183: | ||
let p = primal::StreamingSieve::nth_prime(10001); |
let p = primal::StreamingSieve::nth_prime(10001); |
||
println!("The 10001st prime is {}.", p); |
println!("The 10001st prime is {}.", p); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The 10001st prime is 104743. |
The 10001st prime is 104743. |
||
</pre> |
|||
=={{header|Scala}}== |
|||
Scala3 ready |
|||
<syntaxhighlight lang="scala">object Prime10001 extends App { |
|||
val oddPrimes: LazyList[Int] = 3 #:: LazyList.from(5, 2) |
|||
.filter(p => oddPrimes.takeWhile(_ <= math.sqrt(p)).forall(p % _ > 0)) |
|||
val primes = 2 #:: oddPrimes |
|||
val index = 10_001 |
|||
println(s"prime($index): " + primes.drop(index - 1).take(1).head) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>prime(10001): 104743 |
|||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
<lang |
<syntaxhighlight lang="sidef">say 10001.prime</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 570: | Line 1,214: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 576: | Line 1,220: | ||
var limit = (n.log * n * 1.2).floor // should be enough |
var limit = (n.log * n * 1.2).floor // should be enough |
||
var primes = Int.primeSieve(limit) |
var primes = Int.primeSieve(limit) |
||
Fmt.print("The $,r prime is $,d.", n, primes[n-1])</ |
Fmt.print("The $,r prime is $,d.", n, primes[n-1])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 584: | Line 1,228: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if odd N > 2 is prime |
||
int N, I; |
int N, I; |
||
[for I:= 3 to sqrt(N) do |
[for I:= 3 to sqrt(N) do |
||
Line 603: | Line 1,247: | ||
]; |
]; |
||
IntOut(0, N); |
IntOut(0, N); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
104743 |
104743 |
||
</pre> |
|||
=={{header|Zig}}== |
|||
<syntaxhighlight lang="zig"> |
|||
const std = @import("std"); |
|||
const stdout = @import("std").io.getStdOut().writer(); |
|||
const limit = 10001; |
|||
fn isPrime(x: usize) bool { |
|||
if (x % 2 == 0) return false; |
|||
var i: usize = 3; |
|||
while (i * i <= x) : (i += 2) { |
|||
if (x % i == 0) return false; |
|||
} |
|||
return true; |
|||
} |
|||
pub fn main() !void { |
|||
var cnt: usize = 0; |
|||
var last: usize = 0; |
|||
var n: usize = 1; |
|||
while (cnt < limit) : (n += 1) { |
|||
if (isPrime(n)) { |
|||
cnt += 1; |
|||
last = n; |
|||
} |
|||
} |
|||
try stdout.print("{d}st prime number is: {d}\n", .{ limit, last }); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10001st prime number is: 104743 |
|||
</pre> |
</pre> |
Latest revision as of 10:26, 15 April 2024
- Task
Find and show on this page the 10001st prime number.
11l
V k = 10001
V n = k * 17
V primes = [1B] * n
primes[0] = primes[1] = 0B
L(i) 2 .. Int(sqrt(n))
I !primes[i]
L.continue
L(j) (i * i .< n).step(i)
primes[j] = 0B
L(i) 0 .< n
I primes[i]
I k == 1
print(i)
L.break
k--
- Output:
104743
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
OD
END
- Output:
Prime 10001 is 104743
Arturo
primes: select 2..110000 => prime?
print primes\[10000]
- Output:
104743
AWK
Converted from FreeBASIC
# syntax: GAWK -f 10001TH_PRIME.AWK
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)
}
Idiomatic
# awk -f 10001prime.awk
# n: odd number and n>8
function IsOddPrime(n, i,limit) {
limit = int(sqrt(n))
for (i=3;i <= limit;i+=2)
if (n%i==0) return 0
return 1
}
# pos: positive
function PrimePosition(pos, prime){
pos -= ( (pos==1) ? prime=2 : prime=3 ) - 1
while (pos)
if (IsOddPrime(prime+=2)) pos--
return prime
}
BEGIN { print PrimePosition(10001) }
- 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
Chipmunk Basic
The GW-BASIC solution works without any changes.
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
Gambas
'Use "isprime.bas"
Public Sub Main()
Print prime(10001)
End
Function prime(n As Integer) As Long
If n = 1 Then Return 2
Dim p As Integer = 3, pn As Integer = 1
While pn < n
If isPrime(p) Then pn += 1
p += 2
Wend
Return p - 2
End Function
- 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
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()
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
True BASIC
Trial Division Method
LET max = 10001
LET n = 1
LET p = 0
DO WHILE n <= max
LET f = 0
LET j = 2
DO WHILE f < 1
IF j >= p^0.5 THEN LET f = 2
IF REMAINDER(p, j) = 0 THEN LET f = 1
LET j = j+1
LOOP
IF f <> 1 THEN LET n = n+1
LET p = p+1
LOOP
PRINT p-1
END
- Output:
104743
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
bc
a[0] = 2
a[o = 1] = 3
for (n = 5; o < 10000; n += 2) {
for (i = 1; n % (p = a[i]) != 0; ++i) {
if (p * p > n) {
a[++o] = n
break
}
}
}
a[o]
- Output:
104743
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++
#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.
Dart
import 'dart:math';
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) return false;
}
return true;
}
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;
}
void main() {
print(prime(10001));
}
- Output:
104743
Delphi
function IsPrime(N: integer): boolean;
{Fast, optimised prime test}
var I,Stop: integer;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function Find10001thPrime: integer;
{Return the 10,001th prime number}
var Count: integer;
begin
Count:=1;
Result:= 3;
while true do
begin
if IsPrime(Result) then Count:= Count+1;
if Count=10001 then exit;
Inc(Result,2);
end;
end;
- Output:
10,001th Prime= 104,743
D
import std.stdio;
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 ) {
if(n==1) return 2;
int p, pn=1;
for(p=3;pn<n;p+=2) {
if(isprime(p)) pn++;
}
return p-2;
}
void main()
{
writeln(prime(10_001));
}
- Output:
104743
Erlang
-module(task_10001th_prime).
-export([main/0]).
% 2 and 3 are both primes, so we start searching at 5
main() -> search(5, 2, 2).
search(N, Inc, Count) when Count < 10_001 ->
case is_prime(N) of
true -> search(N + Inc, 6 - Inc, Count + 1);
false -> search(N + Inc, 6 - Inc, Count)
end;
search(N, Inc, _) -> N - 6 + Inc.
is_prime(P) -> is_prime(P, 5, 2).
is_prime(N, P, _) when P * P > N -> true;
is_prime(N, P, _) when N rem P =:= 0 -> false;
is_prime(N, P, Inc) -> is_prime(N, P + Inc, 6 - Inc).
- Output:
timer:tc(task_10001th_prime, main, []). {68615,104743}
EasyLang
fastfunc isprim num .
if num mod 2 = 0 and num > 2
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
i = 2
repeat
if isprim i = 1
nprim += 1
.
until nprim = 10001
i += 1
.
print i
- Output:
104743
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
Frink
nth[primes[], 10001-1]
- Output:
104743
FutureBasic
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
local fn Prime( n as NSUInteger ) as long
long p = 3, pn = 1
if n = 1 then exit fn = 2
while ( pn < n )
if fn IsPrime( p ) then pn++
p += 2
wend
p -= 2
end fn = p
print fn Prime(10001)
HandleEvents
- 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.
JavaScript
Prime 10001 from Russia jdoodle.com/h/2V1
var max = 10001, n=1, p=1; var f,j,s
while (n <= max)
{ f=0; j=2; s = parseInt(Math.pow(p, 0.5))
while (f < 1)
{ if (j >= s) f=2
if ( p % j == 0 ) f=1
j++
}
if (f != 1) n++ // { document.write(n +" "+ p +"<br>") }
p++
}
document.write("<br>"+ (n-1) +" "+ (p-1) +"<br>" )
- Output:
10001 104743
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
Maxima
primes_first_n(n) := (
if n<=1 then
[]
else (
L : [2],
for i:2 thru n do (
L : append(L, [next_prime(last(L))])
),
L
)
)$
last(primes_first_n(10001));
- Output:
104743
MiniScript
isPrime = function(n)
s = floor(n ^ 0.5)
for i in range(2, s)
if n % i == 0 then return false
end for
return true
end function
tt = time
c = 2
p = 2
lastPrime = 2
while c < 10001
p += 1
if isPrime(p) then
c += 1
end if
end while
print p
- Output:
104743
Nim
func isPrime(n: Positive): bool =
## Return true if "n" is prime.
## Assume n >= 5 and n not multiple of 2 and 3.
var d = 5
var step = 2
while d * d <= n:
if n mod d == 0:
return false
inc d, step
step = 6 - step
result = true
iterator primes(): tuple[rank, value: int] =
## Yield the primes preceded by their rank in the sequence.
yield (1, 2)
yield (2, 3)
var idx = 2
var n = 5
var step = 2
while true:
if n.isPrime:
inc idx
yield (idx, n)
inc n, step
step = 6 - step
for (i, n) in primes():
if i == 10001:
echo "10001st prime: ", n
break
- Output:
10001st prime: 104743
OCaml
Using the function seq_primes
from Extensible prime generator#OCaml:
let () =
seq_primes |> Seq.drop 10000 |> Seq.take 1 |> Seq.iter (Printf.printf "%u\n")
- Output:
104743
PARI/GP
prime(10001)
- Output:
%1 = 104743
Pascal
Free Pascal
Program nth_prime;
Function nthprime(x : uint32): uint32;
Var primes : array Of uint32;
i,pr,count : uint32;
found : boolean;
Begin
setlength(primes, x);
primes[1] := 2;
count := 1;
i := 3;
Repeat
found := FALSE;
pr := 0;
Repeat
inc(pr);
found := i Mod primes[pr] = 0;
Until (primes[pr]*primes[pr] > i) Or found;
If Not found Then
Begin
inc(count);
primes[count] := i;
End;
inc(i,2);
Until count = x;
nthprime := primes[x];
End;
Begin
writeln(nthprime(10001));
End.
- Output:
104743
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);
- 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
Prolog
for swi-prolog
isPrime(2). % prime generator
isPrime(N):-
between(3, inf, N),
N /\ 1 > 0, % odd
M is floor(sqrt(N)) - 1, % reverse 2*I+1
Max is M div 2,
forall(between(1, Max, I), N mod (2*I+1) > 0).
do:- Index is 10001,
findnsols(Index, N, isPrime(N), PrimeList),!,
last(PrimeList, PrimeAtIndex),
format('prime(~d) is ~d', [Index, PrimeAtIndex]), nl.
- Output:
?- do. prime(10001) is 104743 true.
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
Quackery
The 10001st prime number is the 10000th odd prime number.
prime
is defined at Miller–Rabin primality test#Quackery.
1 10000 times [ 2 + dup prime until ] echo
- Output:
104743
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...
RPL
« 2
1 10000 START NEXTPRIME NEXT
» 'TASK' STO
- Output:
1: 104743
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.
Scala
Scala3 ready
object Prime10001 extends App {
val oddPrimes: LazyList[Int] = 3 #:: LazyList.from(5, 2)
.filter(p => oddPrimes.takeWhile(_ <= math.sqrt(p)).forall(p % _ > 0))
val primes = 2 #:: oddPrimes
val index = 10_001
println(s"prime($index): " + primes.drop(index - 1).take(1).head)
}
- Output:
prime(10001): 104743
Sidef
say 10001.prime
- Output:
104743
Wren
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
Zig
const std = @import("std");
const stdout = @import("std").io.getStdOut().writer();
const limit = 10001;
fn isPrime(x: usize) bool {
if (x % 2 == 0) return false;
var i: usize = 3;
while (i * i <= x) : (i += 2) {
if (x % i == 0) return false;
}
return true;
}
pub fn main() !void {
var cnt: usize = 0;
var last: usize = 0;
var n: usize = 1;
while (cnt < limit) : (n += 1) {
if (isPrime(n)) {
cnt += 1;
last = n;
}
}
try stdout.print("{d}st prime number is: {d}\n", .{ limit, last });
}
- Output:
10001st prime number is: 104743
- Draft Programming Tasks
- 11l
- ALGOL 68
- ALGOL 68-primes
- Arturo
- AWK
- BASIC
- BASIC256
- Chipmunk Basic
- FreeBASIC
- Gambas
- GW-BASIC
- PureBasic
- QB64
- True BASIC
- Yabasic
- Bc
- C
- C sharp
- C++
- Primesieve
- Dart
- Delphi
- None
- D
- Erlang
- EasyLang
- F Sharp
- Factor
- Fermat
- Frink
- FutureBasic
- Go
- J
- Java
- JavaScript
- Jq
- Julia
- Mathematica
- Wolfram Language
- Maxima
- MiniScript
- Nim
- OCaml
- PARI/GP
- Pascal
- Free Pascal
- Perl
- Ntheory
- Phix
- Picat
- Prolog
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Zig