Category talk:Wren-math: Difference between revisions
→Source code: Int.isPrime now switches automatically from wheel to MR for n >= 2^32.
(→Source code: Fixed a bug in Int.primeCount.) |
(→Source code: Int.isPrime now switches automatically from wheel to MR for n >= 2^32.) |
||
Line 335:
static binomial(n, k) { multinomial(n, [k, n-k]) }
// Private helper method for 'isPrime' method.
// Determines whether 'n' is prime using a wheel with basis [2, 3, 5].▼
// Not accessing the wheel via a list improves performance by about 25%.▼
static isPrime(n) {▼
if (!n.isInteger || n < 2) return false▼
if (n%2 == 0) return n == 2▼
if (n%3 == 0) return n == 3▼
if (n%5 == 0) return n == 5▼
var d = 7▼
while (d*d <= n) {▼
if (n%d == 0) return false▼
d = d + 4▼
if (n%d == 0) return false▼
d = d + 2▼
if (n%d == 0) return false▼
d = d + 4▼
if (n%d == 0) return false▼
d = d + 2▼
if (n%d == 0) return false ▼
d = d + 4▼
if (n%d == 0) return false▼
d = d + 6▼
if (n%d == 0) return false ▼
d = d + 2▼
if (n%d == 0) return false▼
d = d + 6▼
if (n%d == 0) return false ▼
}▼
return true▼
}▼
// Returns true if 'n' is prime, false otherwise but uses the
// Miller-Rabin test which should be faster for 'n' >= 2 ^ 32.
static
if (n%2 == 0) return n == 2
if (n%3 == 0) return n == 3
if (n%5 == 0) return n == 5
if (n%7 == 0) return n == 7
if (n < 121) return true▼
var a
if (n < 2047) {
Line 423 ⟶ 392:
}
}
▲ }
▲ return true
▲ }
▲ // Determines whether 'n' is prime using a wheel with basis [2, 3, 5].
▲ // Not accessing the wheel via a list improves performance by about 25%.
// Automatically changes to Miller-Rabin approach if 'n' >= 2 ^ 32.
▲ static isPrime(n) {
▲ if (!n.isInteger || n < 2) return false
▲ if (n%2 == 0) return n == 2
▲ if (n%3 == 0) return n == 3
▲ if (n%5 == 0) return n == 5
▲ var d = 7
▲ while (d*d <= n) {
▲ if (n%d == 0) return false
▲ d = d + 4
▲ if (n%d == 0) return false
▲ d = d + 2
▲ if (n%d == 0) return false
▲ d = d + 4
▲ if (n%d == 0) return false
▲ d = d + 2
▲ if (n%d == 0) return false
▲ d = d + 4
▲ if (n%d == 0) return false
▲ d = d + 6
▲ if (n%d == 0) return false
▲ d = d + 2
▲ if (n%d == 0) return false
▲ d = d + 6
▲ if (n%d == 0) return false
}
return true
Line 433 ⟶ 434:
while (true) {
if (Int.isPrime(n)) return n
n = n + 2
}
| |||