Primality by Wilson's theorem: Difference between revisions

{{trans|Python}}

 

R n > 1 & (n == 2 | (n % 2 & (factorial(n - 1) + 1) % n == 0))

 

V c = 20

print(‘Primes under #.:’.format(c), end' "\n ")

 

{{out}}

 

=={{header|8086 Assembly}}==

org 100h

section .text

section .data

db '*****' ; Space to hold ASCII number for output

 

{{out}}

 

=={{header|Ada}}==

-- Determine primality using Wilon's theorem.

-- Uses the approach from Algol W

end Main;

 

{{output}}

<pre>

{{Trans|ALGOL W}}

As with many samples on this page, applies the modulo operation at each step in calculating the factorial, to avoid needing large integeres.

# find primes using Wilson's theorem: #

# p is prime if ( ( p - 1 )! + 1 ) mod p = 0 #

FOR i TO 100 DO IF is wilson prime( i ) THEN print( ( " ", whole( i, 0 ) ) ) FI OD

{{out}}

<pre>

=={{header|ALGOL W}}==

As with the APL, Tiny BASIC and other samples, this computes the factorials mod p at each multiplication to avoid needing numbers larger than the 32 bit limit.

% find primes using Wilson's theorem: %

% p is prime if ( ( p - 1 )! + 1 ) mod p = 0 %

 

for i := 1 until 100 do if isWilsonPrime( i ) then writeon( i_w := 1, s_w := 0, " ", i );

{{out}}

<pre>

multiplication. This is necessary for the function to work correctly with more than the first few numbers.

 

 

{{out}}

The naive version (using APL's built-in factorial) looks like this:

 

 

But due to loss of precision with large floating-point values, it only works correctly up to number 19 even with ⎕CT set to zero:

Nominally, the AppleScript solution would be as follows, the 'mod n' at every stage of the factorial being to keep the numbers within the range the language can handle:

 

if (n < 2) then return false

set f to n - 1

if (isPrime(n)) then set end of output to n

end repeat

 

{{output}}

 

In fact, though, the modding by n after every multiplication means there are only three possibilities for the final value of f: n - 1 (if n's a prime), 2 (if n's 4), or 0 (if n's any other non-prime). So the test at the end of the handler could be simplified. Another thing is that if f becomes 0 at some point in the repeat, it obviously stays that way for the remaining iterations, so quite a bit of time can be saved by testing for it and returning <tt>false</tt> immediately if it occurs. And if 2 and its multiples are caught before the repeat, any other non-prime will guarantee a jump out of the handler. Simply reaching the end will mean n's a prime.

It turns out too that <tt>false</tt> results only occur when multiplying numbers between √n and n - √n and that only multiplying numbers in this range still leads to the correct outcomes. And if this isn't abusing Wilson's theorem enough, multiples of 2 and 3 can be prechecked and omitted from the "factorial" process altogether, much as they can be skipped in tests for primality by trial division:

 

-- Check for numbers < 2 and 2 & 3 and their multiples.

if (n < 4) then return (n > 1)

return true

 

=={{header|Arturo}}==

 

 

wprime?: function [n][

 

print "Primes below 20 via Wilson's theorem:"

 

{{out}}

2 3 5 7 11 13 17 19</pre>

=={{header|AWK}}==

# syntax: GAWK -f PRIMALITY_BY_WILSONS_THEOREM.AWK

# converted from FreeBASIC

return(fct == n-1)

}

{{out}}

<pre>

==={{header|BASIC256}}===

{{trans|FreeBASIC}}

fct = 1

for i = 2 to n-1

if wilson_prime(i) then print i; " ";

next i

 

==={{header|QBasic}}===

{{works with|Run BASIC}}

{{trans|FreeBASIC}}

fct = 1

FOR i = 2 TO n - 1

FOR i = 2 TO 100

IF wilsonprime(i) THEN PRINT i; " ";

 

==={{header|PureBasic}}===

{{trans|FreeBASIC}}

fct.i = 1

For i.i = 2 To n-1

PrintN("")

Input()

 

==={{header|Run BASIC}}===

{{works with|QBasic}}

{{trans|FreeBASIC}}

for i = 2 to 100

if wilsonprime(i) = 1 then print i; " ";

next i

if fct = n-1 then wilsonprime = 1 else wilsonprime = 0

 

==={{header|True BASIC}}===

LET fct = 1

FOR i = 2 TO n - 1

IF wilsonprime(i) = 1 THEN PRINT i; " ";

NEXT i

 

==={{header|Yabasic}}===

{{trans|FreeBASIC}}

for i = 2 to 100

if wilson_prime(i) print i, " ";

next i

if fct = n-1 then return True else return False : fi

 

 

=={{header|C}}==

#include <stdint.h>

#include <stdio.h>

 

return 0;

{{out}}

<pre>Is 2 prime: 1

{{libheader|System.Numerics}}

Performance comparison to Sieve of Eratosthenes.

using System.Linq;

using System.Collections;

WriteLine(); WriteLine("\nTime taken: {0}ms\n", (DateTime.Now - st).TotalMilliseconds);

}

{{out|Output @ Tio.run}}

<pre style="white-space: pre-wrap;">--- Wilson's theorem method ---

 

=={{header|C++}}==

#include <iostream>

 

}

}

 

{{out}}

 

=={{header|CLU}}==

wilson = proc (n: int) returns (bool)

if n<2 then return (false) end

end

stream$putl(po, "")

{{out}}

<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</pre>

=={{header|Common Lisp}}==

 

(defun factorial (n)

(if (< n 2) 1 (* n (factorial (1- n)))) )

(unless (zerop n)

(zerop (mod (1+ (factorial (1- n))) n)) ))

 

{{out}}

 

=={{header|Cowgol}}==

 

# Wilson primality test

i := i + 1;

end loop;

 

{{out}}

=={{header|D}}==

{{trans|Java}}

import std.stdio;

 

}

writeln;

{{out}}

<pre>Primes less than 100 testing by Wilson's Theorem

{{trans|Pascal}}

A translation of the Pascal short-cut algorithm, for 17-bit) EDSAC signed integers. Finding primes in the range 65436..65536 took 80 EDSAC minutes, so there is not much point in implementing the unshortened algorithm or extending to 35-bit integers.

[Primes by Wilson's Theoem, for Rosetta Code.]

[EDSAC program, Initial Orders 2.]

PF [acc = 0 on entry]

[end]

{{out}}

<pre>

 

=={{header|Erlang}}==

#! /usr/bin/escript

 

io:format("The first few primes (via Wilson's theorem) are: ~n~p~n",

[[K || K <- lists:seq(1, 128), isprime(K)]]).

{{Out}}

<pre>

 

=={{header|F_Sharp|F#}}==

// Wilsons theorem. Nigel Galloway: August 11th., 2020

let wP(n,g)=(n+1I)%g=0I

let fN=Seq.unfold(fun(n,g)->Some((n,g),((n*g),(g+1I))))(1I,2I)|>Seq.filter wP

fN|>Seq.take 120|>Seq.iter(fun(_,n)->printf "%A " n);printfn "\n"

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.99 2020-08-14}}

math.factorials math.functions prettyprint sequences ;

 

"1000th through 1015th primes:" print

16 primes 999 [ cdr ] times ltake list>array

{{out}}

<pre>

 

=={{header|Fermat}}==

 

=={{header|Forth}}==

: fac-mod ( n m -- r )

>r 1 swap

: .primes ( n -- )

cr 2 ?do i ?prime if i . then loop ;

{{Out}}

<pre>

 

=={{header|FreeBASIC}}==

dim as uinteger fct=1, i

for i = 2 to n-1

for i as uinteger = 2 to 100

if wilson_prime(i) then print i,

{{out}}

Primes below 100

 

=={{Header|GAP}}==

# p is prime if ( ( p - 1 )! + 1 ) mod p = 0

prime := [];

for i in [ -4 .. 100 ] do if isWilsonPrime( i ) then Add( prime, i ); fi; od;

 

{{out}}

 

Presumably we're not allowed to make any trial divisions here except by the number two where all even positive integers, except two itself, are obviously composite.

 

import (

}

fmt.Println()

 

{{out}}

 

=={{header|Haskell}}==

import Data.List

 

top = replicate (length hr) hor

bss = map (\ps -> map (flip replicate ' ') $ zipWith (-) ms ps) $ vss

{{out}}

<pre>

 

=={{header|J}}==

wilson=: 0 = (| !&.:<:)

(#~ wilson) x: 2 + i. 30

2 3 5 7 11 13 17 19 23 29 31

 

=={{header|Java}}==

Wilson's theorem is an ''extremely'' inefficient way of testing for primality. As a result, optimizations such as caching factorials not performed.

import java.math.BigInteger;

 

 

}

 

{{out}}

 

''''Adapted from Julia and Nim''''

def facmod($n; $m):

reduce range(2; $n+1) as $k (1; (. * $k) % $m);

# Notice that `infinite` can be used as the second argument of `range`:

"First 10 primes after 7900:",

{{out}}

Prime numbers between 2 and 100:

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

First 10 primes after 7900:

 

=={{header|Julia}}==

 

wilsonprimesbetween(n, m) = [i for i in n:m if iswilsonprime(i)]

println("First 120 Wilson primes: ", wilsonprimesbetween(1, 1000)[1:120])

println("\nThe first 40 Wilson primes above 7900 are: ", wilsonprimesbetween(7900, 9000)[1:40])

<pre>

First 120 Wilson primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659]

 

=={{header|Lua}}==

function isWilsonPrime( n )

io.write( " " .. n )

end

{{out}}

<pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

WilsonPrimeQ[1] = False;

WilsonPrimeQ[p_Integer] := Divisible[(p - 1)! + 1, p]

{{out}}

Prime factors up to a 100:

 

=={{header|Nim}}==

 

proc facmod(n, m: int): int =

 

echo "Prime numbers between 2 and 100:"

 

{{out}}

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

 

(2) Short cut, based on an observation in the AppleScript solution: if during the calculation of (n - 1)! a partial product is divisible by n, then n is not prime. In fact it suffices for a partial product and n to have a common factor greater than 1. Further, such a common factor must be present in s!, where s = floor(sqrt(n)). Having got s! modulo n we find its HCF with n by Euclid's algorithm; then n is prime if and only if the HCF is 1.

program PrimesByWilson;

uses SysUtils;

ShowPrimes( @WilsonShortCut, 4294967195, 4294967295 {= 2^32 - 1});

end.

{{out}}

<pre>

=={{header|Perl}}==

{{libheader|ntheory}}

use warnings;

use feature 'say';

 

say $ends_in_3;

{{out}}

<pre>3 13 23 43 53 73 83 103 113 163 173 193 223 233 263 283 293 313 353 373 383 433 443 463 503

=={{header|Phix}}==

Uses the modulus method to avoid needing gmp, which was in fact about 7 times slower (when calculating the full factorials).

<span style="color: #008080;">function</span> <span style="color: #000000;">wilson</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">facmod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" '' builtin: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">get_primes</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1015</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">..</span><span style="color: #000000;">1015</span><span style="color: #0000FF;">]})</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

 

=={{header|Plain English}}==

Start up.

Show some primes (via Wilson's theorem).

Find a factorial of the number minus 1. Bump the factorial.

If the factorial is evenly divisible by the number, say yes.

{{out}}

<pre>

 

=={{header|PL/I}}==

wilson: procedure options( main );

declare n binary(15)fixed;

end;

end;

{{out}}

<pre>

=={{header|PL/M}}==

{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)

/* P IS PRIME IF ( ( P - 1 )! + 1 ) MOD P = 0 */

 

END;

 

{{out}}

<pre>

The PL/I include file "pg.inc" can be found on the [[Polyglot:PL/I and PL/M]] page.

Note the use of text in column 81 onwards to hide the PL/I specifics from the PL/M compiler.

wilson_100H: procedure options (main);

 

END;

 

{{out}}

<pre>

=={{header|Python}}==

No attempt is made to optimise this as this method is a [https://en.wikipedia.org/wiki/Wilson%27s_theorem#Primality_tests very poor primality test].

 

def is_wprime(n):

c = int(input('Enter upper limit: '))

print(f'Primes under {c}:')

 

{{out}}

=={{header|Quackery}}==

 

 

[ dup 2 < iff

500 times

[ i^ prime if

 

{{out}}

Not a particularly recommended way to test for primality, especially for larger numbers. It ''works'', but is slow and memory intensive.

 

 

sub is-wilson-prime (Int $p where * > 1) { (($p - 1)! + 1) %% $p }

 

put "\n1000th through 1015th primes:";

{{out}}

<pre> p prime?

 

Also, a "pretty print" was used to align the displaying of a list.

parse arg LO zz /*obtain optional arguments from the CL*/

if LO=='' | LO=="," then LO= 120 /*Not specified? Then use the default.*/

oo= oo _ /*display a line. */

end /*k*/ /*does pretty print.*/

Programming note: &nbsp; This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program &nbsp; (or

BIF) &nbsp; which is used to determine the screen width

 

=={{header|Ring}}==

load "stdlib.ring"

 

ok

next

Output:

<pre>

 

Alternative version computing the factorials modulo n so as to avoid overflow.

 

limit = 100

fmodp %= n

next i

 

{{out}}

 

=={{header|Ruby}}==

return false if i < 2

((1..i-1).inject(&:*) + 1) % i == 0

 

p (1..100).select{|n| w_prime?(n) }

{{out}}

<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

 

=={{header|Rust}}==

let mut f = 1;

while n != 0 && f != 0 {

p += 1;

}

 

{{out}}

 

=={{header|Sidef}}==

n > 1 || return false

(n-1)! % n == n-1

 

say is_wilson_prime_fast(2**43 - 1) #=> false

 

=={{header|Swift}}==

Using a BigInt library.

 

 

func factorial<T: BinaryInteger>(_ n: T) -> T {

}

 

 

{{out}}

 

=={{header|Tiny BASIC}}==

INPUT N

IF N < 0 THEN LET N = -N

40 REM zero and one are nonprimes by definition

PRINT "It is not prime"

 

=={{header|Wren}}==

{{libheader|Wren-fmt}}

Due to a limitation in the size of integers which Wren can handle (2^53-1) and lack of big integer support, we can only reliably demonstrate primality using Wilson's theorem for numbers up to 19.

import "/fmt" for Fmt

 

for (p in 1..19) {

Fmt.print("$2d -> $s", p, wilson.call(p) ? "prime" : "not prime")

 

{{out}}

=={{header|zkl}}==

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library and primes

fcn isWilsonPrime(p){

if(p<=1 or (p%2==0 and p!=2)) return(False);

BI(p-1).factorial().add(1).mod(p) == 0

}

println(" n prime");

println("--- -----");

 

println("\nThe 1,000th to 1,015th prime numbers are:");

{{out}}

<pre>