Rosetta Code

Wilson primes of order n: Difference between revisions

Page Discussion

Wilson primes of order n (view source)

Revision as of 09:39, 10 March 2024

5,687 bytes added ,  2 months ago
m
→‎{{header|RPL}}: removed a debug instruction
(Added C)
m (→‎{{header|RPL}}: removed a debug instruction)
 
(13 intermediate revisions by 8 users not shown)
Line 21:
 
=={{header|ALGOL 68}}==
{{Trans|Visual Basic .NET}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
... but using a sieve for primeallity checking.
{{Trans|Nim}} which is {{Trans|Go}} which is {{Trans|Wren}}
<br>As with the various BASIC samples, all calculations are done MOD p2 so arbitrary precision integers are not needed.
Algol 68G supports long integers, however the precision must be specified.<br>
<syntaxhighlight lang="algol68">
As the memory required for a limit of 11 000 would exceed he maximum supported by Algol 68G under WIndows, a limit of 5 500 is used here, which is sufficient to find all but the 4th order Wilson prime.
<syntaxhighlight lang="algol68">BEGIN # find Wilson primes of order n, primes such that: #
# ( ( n - 1 )! x ( p - n )! - (-1)^n ) mod p^2 = 0 #
INTPR read "primes.incl.a68" PR limit = 5 508; # maxinclude prime to considerutilities #
[]BOOL primes = PRIMESIEVE 11 000; # sieve the primes to 11 500 #
# returns TRUE if p is an nth order Wilson prime #
# Build list of primes. #
PROC is wilson = ( INT n, p )BOOL:
[]INT primes =
BEGIN IF p < n THEN FALSE
ELSE
# sieve the primes to limit^2 which will hopefully be enough for primes #
[LONG 1INT :p2 limit * limit ]BOOL= p * primep;
prime[LONG 1INT ]prod := FALSE; prime[ 2 ] := TRUE1;
FOR i FROMTO n - 1 DO # prod := ( n - 1 )! MOD p2 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;#
FOR i FROM 4 BYprod 2:= TO( UPBprod prime DO prime[* i ] :=) FALSEMOD OD;p2
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI
OD;
FOR i TO p - n DO # countprod := ( ( p - n )! * ( n - 1 the)! primes) upMOD top2 the limit #
INT p count prod := 0;( FORprod i TO limit DO IF prime[* i ] THEN p count +:= 1) FIMOD OD;p2
# construct a list of the primes #OD;
[0 = ( p2 + prod + IF ODD n THEN 1 :ELSE -1 pFI count) ]INTMOD primes;p2
FI # is INTwilson p# pos := 0;
FOR i WHILE p pos < UPB primes DO IF prime[ i ] THEN primes[ p pos +:= 1 ] := i FI OD;
primes
END;
 
# Build list of factorials. #
PR precision 20000 PR # set the number of digits for a LONG LONG INT #
[ 0 : primes[ UPB primes ] ]LONG LONG INT facts;
facts[ 0 ] := 1; FOR i TO UPB facts DO facts[ i ] := facts[ i - 1 ] * i OD;
 
# find the Wilson primes #
INT sign := 1;
print( ( " n: Wilson primes", newline ) );
print( ( "-----------------", newline ) );
FOR n TO 11 DO
print( ( whole( n, -2 ), ":" ) );
signIF :=is -wilson( signn, 2 ) THEN print( ( " 2" ) ) FI;
LONGFOR LONGp INTFROM f3 nBY minus2 1TO =UPB facts[primes n - 1 ];DO
FOR p pos FROM LWBIF primes[ TOp UPB primes] DOTHEN
INT IF is wilson( n, p =) primes[THEN print( ( " ", whole( p, 0 ) ) pos) ];FI
IF p >= n THEN
LONG LONG INT f = f n minus 1 * facts[ p - n ] - sign;
IF f MOD ( p * p ) = 0 THEN print( ( " ", whole( p, 0 ) ) ) FI
FI
OD;
print( ( newline ) )
OD
END
END</syntaxhighlight>
</syntaxhighlight>
{{out}}
<pre>
Line 79 ⟶ 65:
2: 2 3 11 107 4931
3: 7
4: 10429
5: 5 7 47
6: 11
Line 88 ⟶ 74:
11: 17 2713
</pre>
 
 
=={{header|BASIC}}==
Line 265 ⟶ 250:
==={{header|MSX Basic}}===
Both the [[#GW-BASIC|GW-BASIC]] and [[#Chipmunk_Basic|Chipmunk Basic]] solutions work without change.
 
==={{header|Visual Basic .NET}}===
{{Trans|QBasic}}
...but includes 2 and the 4th order Wilson Prime.
<syntaxhighlight lang="vbnet">
Option Strict On
Option Explicit On
 
Module WilsonPrimes
 
Function isPrime(p As Integer) As Boolean
If p < 2 Then Return False
If p Mod 2 = 0 Then Return p = 2
IF p Mod 3 = 0 Then Return p = 3
Dim d As Integer = 5
Do While d * d <= p
If p Mod d = 0 Then
Return False
Else
d = d + 2
End If
Loop
Return True
End Function
 
Function isWilson(n As Integer, p As Integer) As Boolean
If p < n Then Return False
Dim prod As Long = 1
Dim p2 As Long = p * p
For i = 1 To n - 1
prod = (prod * i) Mod p2
Next i
For i = 1 To p - n
prod = (prod * i) Mod p2
Next i
prod = (p2 + prod - If(n Mod 2 = 0, 1, -1)) Mod p2
Return prod = 0
End Function
 
Sub Main()
Console.Out.WriteLine(" n: Wilson primes")
Console.Out.WriteLine("----------------------")
For n = 1 To 11
Console.Out.Write(n.ToString.PadLeft(2) & ": ")
If isWilson(n, 2) Then Console.Out.Write("2 ")
For p = 3 TO 10499 Step 2
If isPrime(p) And isWilson(n, p) Then Console.Out.Write(p & " ")
Next p
Console.Out.WriteLine()
Next n
End Sub
 
End Module
</syntaxhighlight>
{{out}}
<pre>
n: Wilson primes
----------------------
1: 5 13 563
2: 2 3 11 107 4931
3: 7
4: 10429
5: 5 7 47
6: 11
7: 17
8:
9: 541
10: 11 1109
11: 17 2713
</pre>
 
==={{header|Yabasic}}===
Line 303 ⟶ 358:
if prod = 0 then return True else return False : fi
end sub</syntaxhighlight>
 
 
=={{header|C}}==
Line 455 ⟶ 509:
11 | 17 2713
</pre>
 
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func is_wilson n p .
if p < n
return 0
.
prod = 1
p2 = p * p
for i = 1 to n - 1
prod = prod * i mod p2
.
for i = 1 to p - n
prod = prod * i mod p2
.
prod = (p2 + prod - pow -1 n) mod p2
if prod = 0
return 1
.
return 0
.
print "n: Wilson primes"
print "-----------------"
for n = 1 to 11
write n & " "
for p = 3 step 2 to 10099
if isprim p = 1 and is_wilson n p = 1
write p & " "
.
.
print ""
.
</syntaxhighlight>
 
 
=={{header|F_Sharp|F#}}==
Line 674 ⟶ 773:
3010 PROD# = PROD# - INT(PROD#/P2)*P2
3020 RETURN</syntaxhighlight>
 
=={{header|J}}==
<syntaxhighlight lang="j"> wilson=. 0 = (*:@] | _1&^@[ -~ -~ *&! <:@[)^:<:
(>: i. 11x) ([ ;"0 wilson"0/ <@# ]) i.&.(p:inv) 11000
┌──┬───────────────┐
│1 │5 13 563 │
├──┼───────────────┤
│2 │2 3 11 107 4931│
├──┼───────────────┤
│3 │7 │
├──┼───────────────┤
│4 │10429 │
├──┼───────────────┤
│5 │5 7 47 │
├──┼───────────────┤
│6 │11 │
├──┼───────────────┤
│7 │17 │
├──┼───────────────┤
│8 │ │
├──┼───────────────┤
│9 │541 │
├──┼───────────────┤
│10│11 1109 │
├──┼───────────────┤
│11│17 2713 │
└──┴───────────────┘</syntaxhighlight>
 
=={{header|Java}}==
Line 900 ⟶ 1,027:
10: 11 1109
11: 17 2713</pre>
 
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
default("parisizemax", "1024M");
 
 
\\ Define the function wilsonprimes with a default limit of 11000
wilsonprimes(limit) = {
\\ Set the default limit if not specified
my(limit = if(limit, limit, 11000));
\\ Precompute factorial values up to the limit to save time
my(facts = vector(limit, i, i!));
\\ Sign variable for adjustment in the formula
my(sgn = 1);
print(" n: Wilson primes\n--------------------");
\\ Loop over the specified range (1 to 11 in the original code)
for(n = 1, 11,
print1(Str(" ", n, ": "));
sgn = -sgn; \\ Toggle the sign
\\ Loop over all primes up to the limit
forprime(p = 2, limit,
\\ Check the Wilson prime condition modified for PARI/GP
index=1;
if(n<2,index=1,index=n-1);
if(p > n && Mod(facts[index] * facts[p - n] - sgn, p^2) == 0,
print1(Str(p, " "));
)
);
print1("\n");
);
}
 
\\ Execute the function with the default limit
wilsonprimes();
</syntaxhighlight>
 
{{out}}
<pre>
n: Wilson primes
--------------------
1: 5 13 563
2: 3 11 107 4931
3: 7
4: 10429
5: 7 47
6: 11
7: 17
8:
9: 541
10: 11 1109
11: 17 2713
 
</pre>
 
=={{header|Perl}}==
Line 1,061 ⟶ 1,242:
11 | 17 2713
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">
# wilson_prime.py by xing216
def sieve(n):
multiples = []
for i in range(2, n+1):
if i not in multiples:
yield i
for j in range(i*i, n+1, i):
multiples.append(j)
def intListToString(list):
return " ".join([str(i) for i in list])
limit = 11000
primes = list(sieve(limit))
facs = [1]
for i in range(1,limit):
facs.append(facs[-1]*i)
sign = 1
print(" n: Wilson primes")
print("—————————————————")
 
for n in range(1,12):
sign = -sign
wilson = []
for p in primes:
if p < n: continue
f = facs[n-1] * facs[p-n] - sign
if f % p**2 == 0: wilson.append(p)
print(f"{n:2d}: {intListToString(wilson)}")
</syntaxhighlight>
{{out}}
<pre>
n: Wilson primes
—————————————————
1: 5 13 563
2: 2 3 11 107 4931
3: 7
4: 10429
5: 5 7 47
6: 11
7: 17
8:
9: 541
10: 11 1109
11: 17 2713
</pre>
=={{header|Racket}}==
 
Line 1,223 ⟶ 1,449:
11 │ 17 2,713
───────┴─────────────────────────────────────────────────────────────
</pre>
 
=={{header|RPL}}==
{{works with|RPL|HP-49C}}
« → maxp
« { }
1 11 '''FOR''' n
{ } n
'''IF''' DUP ISPRIME? NOT '''THEN''' NEXTPRIME '''END'''
'''WHILE''' DUP maxp < '''REPEAT'''
n 1 - FACT OVER n - FACT * -1 n ^ -
'''IF''' OVER SQ MOD NOT '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END'''
DROP 1 →LIST +
'''NEXT'''
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { { 5 13 } { 2 3 11 } { 7 } { } { 5 7 } { 11 } { 17 } { } { } { 11 } { 17 } }
</pre>
 
Line 1,259 ⟶ 1,505:
 
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
Line 1,376 ⟶ 1,623:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./big" for BigInt
import "./fmt" for Fmt
 
var limit = 11000
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339723...361583"