10001th prime: Difference between revisions
m (→{{header|C#|CSharp}}: not sure why "@ Tio.run" was removed, added "trial division" mention.) |
|||
Line 201:
=={{header|C#|CSharp}}==
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 {
Line 214:
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;
Line 230:
Console.Write(" {0:n0} {1} μs {2:0.000} times faster", t,
(e2 = sw.Elapsed.TotalMilliseconds) * 1000.0, e1 / e2); } }</lang>
{{out|Output @ Tio.run}}
<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>
=={{header|C#|CSharp}}==
|
Revision as of 16:56, 8 June 2022
- 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.
<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>
- syntax: GAWK -f 10001TH_PRIME.AWK
- 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>
- 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 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.
<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 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); } }</lang>
- 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
C#
<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(); }}}</lang>
- Output:
104743
C++
<lang cpp>#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";
}</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>
- 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 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));
- The task
- 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
<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
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; # 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())</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
<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