Primality by Wilson's theorem: Difference between revisions

← Older edit

Primality by Wilson's theorem (view source)

Revision as of 14:01, 27 February 2024

8,873 bytes added , 2 months ago

Add Refal

Not a robot

2,093

edits

Revision as of 00:18, 30 April 2023 (view source) EnglishMuffin (talk \| contribs) (Jakt) ← Older edit		Latest revision as of 14:01, 27 February 2024 (view source) Not a robot (talk \| contribs) (Add Refal)
(18 intermediate revisions by 9 users not shown)
Line 390: =={{header\|BASIC}}== ==={{header\|Applesoft BASIC}}=== {{works with\|Chipmunk Basic}} {{works with\|GW-BASIC}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">100 HOME : REM 100 CLS for Chipmunk Basic 110 PRINT "Primes below 100"+CHR$(10) 120 FOR n = 2 TO 100 130 GOSUB 160 140 NEXT n 150 END 160 rem FUNCTION WilsonPrime(n) 170 fct = 1 180 FOR i = 2 TO n-1 181 a = fct * i 190 fct = a - INT(a / n) * n 200 NEXT i 210 IF fct = n-1 THEN PRINT i;" "; 220 RETURN</syntaxhighlight> ==={{header\|BASIC256}}=== {{trans\|FreeBASIC}} Line 405 ⟶ 424: next i end</syntaxhighlight> ==={{header\|Chipmunk Basic}}=== {{works with\|Chipmunk Basic\|3.6.4}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">100 cls 110 print "Primes below 100"+chr$(10) 120 for i = 2 to 100 130 wilsonprime(i) 140 next i 150 end 160 function wilsonprime(n) 170 fct = 1 180 for i = 2 to n-1 190 fct = (fcti) mod n 200 next i 210 if fct = n-1 then print i; 220 end function</syntaxhighlight> ==={{header\|Craft Basic}}=== <syntaxhighlight lang="basic">for i = 2 to 100 let f = 1 for j = 2 to i - 1 let f = (f j) % i wait next j if f = i - 1 then print i endif next i end</syntaxhighlight> {{out\| Output}}<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\|GW-BASIC}}=== {{works with\|Chipmunk Basic}} {{works with\|PC-BASIC\|any}} {{works with\|MSX_Basic}} {{works with\|QBasic}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">100 CLS : REM 100 CLS for Chipmunk Basic 110 PRINT "Primes below 100"+CHR$(10) 120 FOR N = 2 TO 100 130 GOSUB 160 140 NEXT N 150 END 160 REM FUNCTION WilsonPrime(n) 170 FCT = 1 180 FOR I = 2 TO N-1 190 FCT = (FCTI) MOD N 200 NEXT I 210 IF FCT = N-1 THEN PRINT I;" "; 220 RETURN</syntaxhighlight> ==={{header\|Minimal BASIC}}=== {{works with\|QBasic}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">110 PRINT "Primes below 100" 120 FOR n = 2 TO 100 130 GOSUB 160 140 NEXT n 150 GOTO 250 160 rem FUNCTION WilsonPrime(n) 170 LET f = 1 180 FOR i = 2 TO n-1 181 LET a = f i 190 LET f = a - INT(a / n) * n 200 NEXT i 210 IF f = n-1 THEN 230 220 RETURN 230 PRINT i 240 RETURN 250 END</syntaxhighlight> ==={{header\|MSX Basic}}=== The [[#GW-BASIC\|GW-BASIC]] solution works without any changes. ==={{header\|QBasic}}=== Line 423 ⟶ 525: IF wilsonprime(i) THEN PRINT i; " "; NEXT i</syntaxhighlight> ==={{header\|Quite BASIC}}=== {{works with\|QBasic}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">100 CLS 110 PRINT "Primes below 100": PRINT 120 FOR n = 2 TO 100 130 GOSUB 160 140 NEXT n 150 GOTO 250 160 rem FUNCTION WilsonPrime(n) 170 LET f = 1 180 FOR i = 2 TO n-1 181 LET a = f * i 190 LET f = a - INT(a / n) * n 200 NEXT i 210 IF f = n-1 THEN 230 220 RETURN 230 PRINT i;" "; 240 RETURN 250 END</syntaxhighlight> ==={{header\|PureBasic}}=== Line 499 ⟶ 622: =={{header\|BCPL}}== <syntaxhighlight lang="bcpl">get "libhdr" let wilson(n) = valof $( let f = n - 1 if n < 2 then resultis false for i = n-2 to 2 by -1 do f := fi rem n resultis (f+1) rem n = 0 $) let start() be for i = 1 to 100 if wilson(i) do writef("%NN", i)</syntaxhighlight> {{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\|C}}== <syntaxhighlight lang="c">#include <stdbool.h> Line 858 ⟶ 1,021: <pre>Primes less than 100 testing by Wilson's Theorem 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\|Dart}}== {{trans\|Swift}} <syntaxhighlight lang="Dart"> BigInt factorial(BigInt n) { if (n == BigInt.zero) { return BigInt.one; } BigInt result = BigInt.one; for (BigInt i = n; i > BigInt.zero; i = i - BigInt.one) { result = i; } return result; } bool isWilsonPrime(BigInt n) { if (n < BigInt.from(2)) { return false; } return (factorial(n - BigInt.one) + BigInt.one) % n == BigInt.zero; } void main() { var wilsonPrimes = []; for (var i = BigInt.one; i <= BigInt.from(100); i += BigInt.one) { if (isWilsonPrime(i)) { wilsonPrimes.add(i); } } print(wilsonPrimes); } </syntaxhighlight> {{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\|Draco}}== <syntaxhighlight lang="draco">proc wilson(word n) bool: word f, i; if n<2 then false else f := n - 1; for i from n-2 downto 2 do f := (fi) % n od; (f+1) % n = 0 fi corp proc main() void: word i; for i from 1 upto 100 do if wilson(i) then write(i, ' ') fi od corp</syntaxhighlight> {{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\|EasyLang}}== {{trans\|BASIC256}} <syntaxhighlight> func wilson_prime n . fct = 1 for i = 2 to n - 1 fct = fct * i mod n . return if fct = n - 1 . for i = 2 to 100 if wilson_prime i = 1 write i & " " . . </syntaxhighlight> {{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\|EDSAC order code}}== Line 1,135 ⟶ 1,387: 53 59 61 67 71 73 79 83 89 97</pre> =={{header\|FutureBasic}}== <syntaxhighlight lang="futurebasic"> local fn WilsonPrime( n as long ) as BOOL long i, fct = 1 BOOL result for i = 2 to n -1 fct = (fct * i) mod n next i if fct == n - 1 then exit fn = YES else exit fn = NO end fn = result long i print "Primes below 100:" for i = 2 to 100 if fn WilsonPrime(i) then print i next HandleEvents </syntaxhighlight> {{output}} <pre> Primes below 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 </pre> =={{header\|Fōrmulæ}}== {{FormulaeEntry\|page=https://formulae.org/?script=examples/Primality_by_Wilson%27s_theorem}} Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition. '''Solution''' [[File:Fōrmulæ - Primality by Wilson's theorem 01.png]] '''Test cases''' [[File:Fōrmulæ - Primality by Wilson's theorem 02.png]] Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used. [[File:Fōrmulæ - Primality by Wilson's theorem 03.png]] ~~In '''[https://formulae.org/?example=Primality_by_Wilson%27s_theorem this]''' page you can see the program(s) related to this task and their results.~~ =={{Header\|GAP}}== Line 1,485 ⟶ 1,795: 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\|MAD}}== <syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER INTERNAL FUNCTION(N) ENTRY TO WILSON. WHENEVER N.L.2, FUNCTION RETURN 0B F = 1 THROUGH FM, FOR I = N-1, -1, I.L.2 F = FI FM F = F-F/NN FUNCTION RETURN N.E.F+1 END OF FUNCTION PRINT COMMENT $ PRIMES UP TO 100$ THROUGH TEST, FOR V=1, 1, V.G.100 TEST WHENEVER WILSON.(V), PRINT FORMAT NUMF, V VECTOR VALUES NUMF = $I3$ END OF PROGRAM</syntaxhighlight> {{out}} <pre>PRIMES UP TO 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</pre> =={{header\|Mathematica}}/{{header\|Wolfram Language}}== Line 1,494 ⟶ 1,851: Prime factors up to a 100: <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\|Miranda}}== <syntaxhighlight lang="miranda">main :: [sys_message] main = [Stdout (show (filter wilson [1..100]) ++ "\n")] wilson :: num->bool wilson n = False, if n<2 = test (n-1) (n-2), otherwise where test f i = f+1 = n, if i<2 = test (fi mod n) (i-1), otherwise</syntaxhighlight> {{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\|Modula-2}}== <syntaxhighlight lang="modula2">MODULE WilsonPrimes; FROM InOut IMPORT WriteCard, WriteLn; VAR i: CARDINAL; PROCEDURE Wilson(n: CARDINAL): BOOLEAN; VAR f, i: CARDINAL; BEGIN IF n<2 THEN RETURN FALSE END; f := 1; FOR i := n-1 TO 2 BY -1 DO f := fi MOD n END; RETURN f + 1 = n END Wilson; BEGIN FOR i := 1 TO 100 DO IF Wilson(i) THEN WriteCard(i, 3) END END; WriteLn END WilsonPrimes.</syntaxhighlight> {{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\|Nim}}== Line 2,089 ⟶ 2,487: </pre> =={{header\|Refal}}== <syntaxhighlight lang="refal">$ENTRY Go { = <Prout <Filter Wilson <Iota 100>>>; }; Wilson { s.N, <Compare s.N 2>: '-' = F; s.N = <Wilson s.N 1 <- s.N 1>>; s.N s.A 1, <- s.N 1>: { s.A = T; s.X = F; }; s.N s.A s.C = <Wilson s.N <Mod < s.A s.C> s.N> <- s.C 1>>; }; Iota { s.N = <Iota 1 s.N>; s.N s.N = s.N; s.N s.M = s.N <Iota <+ 1 s.N> s.M>; }; Filter { s.F = ; s.F t.I e.X, <Mu s.F t.I>: { T = t.I <Filter s.F e.X>; F = <Filter s.F e.X>; }; };</syntaxhighlight> {{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\|Ring}}== <syntaxhighlight lang="ring"> Line 2,151 ⟶ 2,576: 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\|RPL}}== {{works with\|HP\|48S}} ≪ '''IF''' DUP 1 > '''THEN''' DUP → p j ≪ 1 '''WHILE''' 'j' DECR 1 > '''REPEAT''' j * p MOD '''END''' 1 + p MOD NOT ≫ '''ELSE''' DROP 0 '''END''' ≫ '<span style="color:blue">WILSON?<span>' STO =={{header\|Ruby}}== Line 2,238 ⟶ 2,674: 7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 </pre> =={{header\|Scala}}== {{trans\|Java}} <syntaxhighlight lang="Scala"> import scala.math.BigInt object PrimalityByWilsonsTheorem extends App { println("Primes less than 100 testing by Wilson's Theorem") (0 to 100).foreach(i => if (isPrime(i)) print(s"$i ")) private def isPrime(p: Long): Boolean = { if (p <= 1) return false (fact(p - 1).+(BigInt(1))).mod(BigInt(p)) == BigInt(0) } private def fact(n: Long): BigInt = { (2 to n.toInt).foldLeft(BigInt(1))((fact, i) => fact * BigInt(i)) } } </syntaxhighlight> {{out}} <pre> Primes less than 100 testing by Wilson's Theorem 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\|SETL}}== <syntaxhighlight lang="setl">program wilsons_theorem; print({n : n in {1..100} \| wilson n}); op wilson(p); return p>1 and */{1..p-1} mod p = p-1; end op; end program;</syntaxhighlight> {{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\|Sidef}}== Line 2,314 ⟶ 2,787: =={{header\|Wren}}== {{libheader\|Wren-~~math~~gmp}} {{libheader\|Wren-fmt}} <syntaxhighlight lang="wren">import "./gmp" for Mpz ~~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.~~ ~~<syntaxhighlight lang="ecmascript">~~import "./~~math~~fmt" for ~~Int~~Fmt ~~import "/fmt" for Fmt~~ var t = Mpz.new() var wilson = Fn.new { \|p\| if (p < 2) return false return (~~Int~~t.factorial(p-1) + 1) % p == 0 } var primes = [2] ~~for (p in 1..19) {~~ var i = 3 ~~Fmt.print("$2d -> $s", p, wilson.call(p) ? "prime" : "not prime")~~ while (primes.count < 1015) { ~~}</syntaxhighlight>~~ if (wilson.call(i)) primes.add(i) i = i + 2 } var candidates = [2, 3, 9, 15, 29, 37, 47, 57, 67, 77, 87, 97, 237, 409, 659] System.print(" n \| prime?\n------------") for (cand in candidates) Fmt.print("$3d \| $s", cand, wilson.call(cand)) System.print("\nThe first 120 prime numbers by Wilson's theorem are:") Fmt.tprint("$3d", primes[0..119], 20) System.print("\nThe 1,000th to 1,015th prime numbers are:") System.print(primes[-16..-1].join(" "))</syntaxhighlight> {{out}} <pre> 1 -> ~~not~~n \| prime? ------------ ~~2 -> prime~~ 2 \| true ~~3 -> prime~~ 3 \| true ~~4 -> not prime~~ 9 \| false ~~5 -> prime~~ 15 \| false ~~6 -> not prime~~ 729 ->\| ~~prime~~true 37 \| true ~~8 -> not prime~~ 47 \| true ~~9 -> not prime~~ 57 \| false ~~10 -> not prime~~ 67 \| true ~~11 -> prime~~ 77 \| false ~~12 -> not prime~~ 87 \| false ~~13 -> prime~~ 97 \| true ~~14 -> not prime~~ 237 \| false ~~15 -> not prime~~ 409 \| true ~~16 -> not prime~~ 659 \| true ~~17 -> prime~~ ~~18 -> not prime~~ The first 120 prime numbers by Wilson's theorem are: ~~19 -> prime~~ 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 The 1,000th to 1,015th prime numbers are: 7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 </pre>