Wilson primes of order n: Difference between revisions
m
→{{header|RPL}}: removed a debug instruction
(Wilson primes of order n in Applesoft BASIC, Chipmunk Basic and MSX Basic) |
m (→{{header|RPL}}: removed a debug instruction) |
||
| (14 intermediate revisions by 8 users not shown) | |||
Line 21:
=={{header|ALGOL 68}}==
{{Trans|Visual Basic .NET}}
... but using a sieve for primeallity checking.
<br>As with the various BASIC samples, all calculations are done MOD p2 so arbitrary precision integers are not needed.
<syntaxhighlight lang="algol68">
# ( ( n - 1 )! x ( p - n )! - (-1)^n ) mod p^2 = 0 #
[]BOOL primes = PRIMESIEVE 11 000; # sieve the primes to 11 500 #
# returns TRUE if p is an nth order Wilson prime #
PROC is wilson = ( INT n, p )BOOL:
ELSE
FOR i
OD;
FOR i TO p - n DO #
FI # is
# find the Wilson primes #
print( ( " n: Wilson primes", newline ) );
print( ( "-----------------", newline ) );
FOR n TO 11 DO
print( ( whole( n, -2 ), ":" ) );
FI
OD;
print( ( newline ) )
OD
END
</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 304 ⟶ 359:
end sub</syntaxhighlight>
=={{header|C}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <gmp.h>
bool *sieve(int limit) {
int i, p;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
return c;
}
int main() {
const int limit = 11000;
int i, j, n, pc = 0;
unsigned long p;
bool *c = sieve(limit);
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
unsigned long *primes = (unsigned long *)malloc(pc * sizeof(unsigned long));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
mpz_t *facts = (mpz_t *)malloc(limit *sizeof(mpz_t));
for (i = 0; i < limit; ++i) mpz_init(facts[i]);
mpz_set_ui(facts[0], 1);
for (i = 1; i < limit; ++i) mpz_mul_ui(facts[i], facts[i-1], i);
mpz_t f, sign;
mpz_init(f);
mpz_init_set_ui(sign, 1);
printf(" n: Wilson primes\n");
printf("--------------------\n");
for (n = 1; n < 12; ++n) {
printf("%2d: ", n);
mpz_neg(sign, sign);
for (i = 0; i < pc; ++i) {
p = primes[i];
if (p < n) continue;
mpz_mul(f, facts[n-1], facts[p-n]);
mpz_sub(f, f, sign);
if (mpz_divisible_ui_p(f, p*p)) printf("%ld ", p);
}
printf("\n");
}
free(c);
free(primes);
for (i = 0; i < limit; ++i) mpz_clear(facts[i]);
free(facts);
return 0;
}</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|C++}}==
Line 369 ⟶ 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 588 ⟶ 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 814 ⟶ 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 975 ⟶ 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,137 ⟶ 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,173 ⟶ 1,505:
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
Line 1,290 ⟶ 1,623:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./big" for BigInt
import "./fmt" for Fmt
var limit = 11000
| |||