Primality by Wilson's theorem: Difference between revisions
(→{{header|Go}}: Now generates 1000th to 1015th primes as well to keep Perl 6 company.) |
m (→{{header|Factor}}: fix off-by-one error) |
||
Line 35: | Line 35: | ||
"1000th through 1015th primes:" print |
"1000th through 1015th primes:" print |
||
16 primes |
16 primes 999 [ cdr ] times ltake list>array |
||
[ pprint bl ] each nl</lang> |
[ pprint bl ] each nl</lang> |
||
{{out}} |
{{out}} |
||
Line 66: | Line 66: | ||
1000th through 1015th primes: |
1000th through 1015th primes: |
||
7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 |
7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 |
||
</pre> |
</pre> |
||
Revision as of 15:14, 1 January 2020
- Task
Write a boolean function that tells whether a given integer is prime.
Remember that 1 and all non-positive numbers are not prime.
A number is prime if p divides (p - 1)! + 1
.
Factor
<lang factor>USING: formatting grouping io kernel lists lists.lazy math math.functions memoize prettyprint sequences ;
MEMO: factorial ( m -- n ) ! memoize factorial function
[ 1 ] [ [ 1 - factorial ] [ * ] bi ] if-zero ;
- wilson ( n -- ? ) [ 1 - factorial 1 + ] [ divisor? ] bi ;
- prime? ( n -- ? ) dup 2 < [ drop f ] [ wilson ] if ;
- primes ( -- list ) 1 lfrom [ prime? ] lfilter ;
"n prime?\n--- -----" print { 2 3 9 15 29 37 47 57 67 77 87 97 237 409 659 } [ dup prime? "%-3d %u\n" printf ] each nl
"First 120 primes via Wilson's theorem:" print 120 primes ltake list>array 20 group simple-table. nl
"1000th through 1015th primes:" print 16 primes 999 [ cdr ] times ltake list>array [ pprint bl ] each nl</lang>
- Output:
n prime? --- ----- 2 t 3 t 9 f 15 f 29 t 37 t 47 t 57 f 67 t 77 f 87 f 97 t 237 f 409 t 659 t First 120 primes via 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 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 1000th through 1015th primes: 7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081
Go
Needless to say, Wilson's theorem is an extremely inefficient way of testing for primalty with 'big integer' arithmetic being needed to compute factorials greater than 20.
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. <lang go>package main
import (
"fmt" "math/big"
)
var (
zero = big.NewInt(0) one = big.NewInt(1) prev = big.NewInt(factorial(20))
)
// Only usable for n <= 20. func factorial(n int64) int64 {
res := int64(1) for k := n; k > 1; k-- { res *= k } return res
}
// If memo == true, stores previous sequential // factorial calculation for odd n > 21. func wilson(n int64, memo bool) bool {
if n <= 1 || (n%2 == 0 && n != 2) { return false } if n <= 21 { return (factorial(n-1)+1)%n == 0 } b := big.NewInt(n) r := big.NewInt(0) z := big.NewInt(0) if !memo { z.MulRange(2, n-1) // computes factorial from scratch } else { prev.Mul(prev, r.MulRange(n-2, n-1)) // uses previous calculation z.Set(prev) } z.Add(z, one) return r.Rem(z, b).Cmp(zero) == 0
}
func main() {
numbers := []int64{2, 3, 9, 15, 29, 37, 47, 57, 67, 77, 87, 97, 237, 409, 659} fmt.Println(" n prime") fmt.Println("--- -----") for _, n := range numbers { fmt.Printf("%3d %t\n", n, wilson(n, false)) }
// sequential memoized calculation fmt.Println("\nThe first 120 prime numbers are:") for i, count := int64(2), 0; count < 1015; i += 2 { if wilson(i, true) { count++ if count <= 120 { fmt.Printf("%3d ", i) if count%20 == 0 { fmt.Println() } } else if count >= 1000 { if count == 1000 { fmt.Println("\nThe 1,000th to 1,015th prime numbers are:") } fmt.Printf("%4d ", i) } } if i == 2 { i-- } } fmt.Println()
}</lang>
- Output:
n prime --- ----- 2 true 3 true 9 false 15 false 29 true 37 true 47 true 57 false 67 true 77 false 87 false 97 true 237 false 409 true 659 true The first 120 prime numbers are: 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
Perl 6
Not a particularly recommended way to test for primality, especially for larger numbers. It works, but is slow and memory intensive.
<lang perl6>sub postfix:<!> (Int $n) { (constant f = 1, |[\*] 1..*)[$n] }
sub is-wilson-prime (Int $p where * > 1) { (($p - 1)! + 1) %% $p }
- Pre initialize factorial routine (not thread safe)
9000!;
- Testing
put ' p prime?'; printf("%4d %s\n", $_, .&is-wilson-prime) for 2, 3, 9, 15, 29, 37, 47, 57, 67, 77, 87, 97, 237, 409, 659;
put "\nFirst 120 primes:"; put (2..*).hyper.grep( *.&is-wilson-prime )[^120].rotor(20)».fmt('%3d').join: "\n";
put "\n1000th through 1015th primes:"; put (2..*).hyper.grep( *.&is-wilson-prime )[1000..1015];</lang>
- Output:
p prime? 2 True 3 True 9 False 15 False 29 True 37 True 47 True 57 False 67 True 77 False 87 False 97 True 237 False 409 True 659 True First 120 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 1000th through 1015th primes: 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 8087