Rosetta Code

10001th prime: Difference between revisions

Page Discussion

10001th prime (view source)

Revision as of 10:26, 15 April 2024

8,703 bytes added ,  1 month ago
m
typo
(→‎{{header|Quackery}}: Added an optimisation.)
m (typo)
 
(36 intermediate revisions by 20 users not shown)
Line 6:
 
=={{header|11l}}==
 
<syntaxhighlight lang="11l">V k = 10001
V n = k * 17
Line 55 ⟶ 54:
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">primes: select 2..110000 => prime?
print primes\[10000]</syntaxhighlight>
Line 64 ⟶ 62:
 
=={{header|AWK}}==
==== Converted from FreeBASIC ====
<syntaxhighlight lang="awk">
# syntax: GAWK -f 10001TH_PRIME.AWK
 
# converted from FreeBASIC
BEGIN {
printf("%s\n",main(10001))
Line 97 ⟶ 96:
}
</syntaxhighlight>
 
==== 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}}
<pre>
Line 128 ⟶ 152:
print prime(10001)
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}}===
Line 168 ⟶ 259:
PrintN(Str(n))
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}}===
Line 195 ⟶ 349:
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}}==
Line 299 ⟶ 467:
The 10,001st prime is 104,743.
</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#}}==
Line 320 ⟶ 658:
 
=={{header|Fermat}}==
<syntaxhighlight lang="fermatpascal">
Prime(10001);
</syntaxhighlight>
{{out}}<pre>104743</pre>
 
=={{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>
Line 349 ⟶ 670:
</pre>
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
 
local fn IsPrime( n as NSUInteger ) as BOOL
=={{header|GW-BASIC}}==
BOOL isPrime = YES
<syntaxhighlight lang="gwbasic">10 PN=1
NSUInteger i
20 P = 3
30 WHILE PN < 10001
if n < 2 then exit fn = NO
40 GOSUB 100
50 IF Qif n = 12 THEN PN = PN + 1 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</syntaxhighlight>
wend
{{out}}<pre>104743</pre>
p -= 2
end fn = p
 
print fn Prime(10001)
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
104743
</pre>
 
=={{header|Go}}==
Line 430 ⟶ 764:
<pre>
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>
 
Line 462 ⟶ 820:
104743
</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}}==
<syntaxhighlight lang="parigp">prime(10001)</syntaxhighlight>
{{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}}==
Line 488 ⟶ 976:
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="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)
<!--</syntaxhighlight>-->
</syntaxhighlight>
{{out}}
<pre>
104743
</pre>
 
 
=={{header|Picat}}==
Line 588 ⟶ 1,076:
{{out}}
<pre>10001 104743 7 seconds</pre>
 
=={{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|Quackery}}==
 
The 10001st prime number is the 10000th odd prime number.
 
<code>isprimeprime</code> is defined at [[PrimalityMiller–Rabin byprimality trial divisiontest#Quackery]].
 
<syntaxhighlight lang="Quackery"> 1 10000 times [ 2 + dup isprimeprime until ] echo</syntaxhighlight>
 
{{out}}
Line 712 ⟶ 1,158:
The 10001th prime is: 104743
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>
 
Line 720 ⟶ 1,175:
<pre>104743
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
Line 758 ⟶ 1,214:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
Line 796 ⟶ 1,252:
<pre>
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>
Chrboesch
19

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/334759...363688"