Lucas-Lehmer test: Difference between revisions
Changed the recent entry by one which is ready to run and can handle much more digits
(→{{header|Wren}}: Added an embedded version.) |
(Changed the recent entry by one which is ready to run and can handle much more digits) |
||
Line 3,462:
Uses a sieve of Eratosthenes.
<lang swift>import BigInt // add package attaswift/BigInt from Github
<lang swift>func lucasLehmer(_ p: Int) -> Bool {▼
import Darwin
let m = BigInt(2).power(p) - 1▼
var s = BigInt(4)▼
func Eratosthenes(upTo: Int) -> [Int] {
for _ in 0..<p-2 {▼
s = ((s * s) - 2) % m▼
let maxroot = Int(sqrt(Double(upTo)))
▲ }
var isprime = [Bool](repeating: true, count: upTo+1 )
return s == 0▼
for i in 2...maxroot {
if isprime[i] {
for k in stride(from: upTo/i, through: i, by: -1) {
if isprime[k] {
isprime[i*k] = false }
}
}
}
var result = [Int]()
for i in 2...upTo {
if isprime[i] {
result.append( i)
}
}
return result
}
let m =
▲ var s = BigInt(4)
▲ for _ in 0..<p-2 {
▲ s = ((s * s) - 2) % m
}
▲ return s == 0
}
for
print("2^\(prime) - 1 = \(mprime) is prime")
}</lang>
Line 3,487 ⟶ 3,511:
2^19 - 1 = 524287 is prime
2^31 - 1 = 2147483647 is prime
2^61 - 1 = 2305843009213693951 is prime
2^89 - 1 = 618970019642690137449562111 is prime
2^107 - 1 = 162259276829213363391578010288127 is prime
2^127 - 1 = 170141183460469231731687303715884105727 is prime</pre>
=={{header|Tcl}}==
| |||