Prime decomposition: Difference between revisions
Content deleted Content added
→{{header|Python}}: performance hints |
Added Scala |
||
Line 1,049:
47 : 140737488355327 : [2351, 4513, 13264529]
53 : 9007199254740991 : [6361, 69431, 20394401]</pre>
=={{header|Scala}}==
Getting the prime factors does not require identifying prime numbers. Since
the problems seems to ask for it, here is one version that does it:
<lang scala>class PrimeFactors(n: BigInt) extends Iterator[BigInt] {
def zero = BigInt(0)
def one = BigInt(1)
def two = BigInt(2)
def isPrime(n: BigInt) = n.isProbablePrime(10)
var currentN = n
var prime = two
def nextPrime =
if (prime == two) {
prime += one
} else {
prime += two
while (!isPrime(prime)) {
prime += two
}
}
def next = {
if (!hasNext)
throw new NoSuchElementException("next on empty iterator")
while(currentN % prime != zero) {
nextPrime
}
currentN /= prime
prime
}
def hasNext = currentN != one && currentN > zero
}</lang>
The method isProbablePrime(n) has a chance of 1 - 1/(2^n) of correctly
identifying a prime. Here is a version that does not depend on identifying
primes:
<lang scala>class PrimeFactors2(n: BigInt) extends Iterator[BigInt] {
def zero = BigInt(0)
def one = BigInt(1)
def two = BigInt(2)
var currentN = n
var divisor = two
def next = {
if (!hasNext)
throw new NoSuchElementException("next on empty iterator")
while(currentN % divisor != zero) {
if (divisor == two)
divisor += one
else
divisor += two
}
currentN /= divisor
divisor
}
def hasNext = currentN != one && currentN > zero
}</lang>
Both versions are rather slow, as they accept arbitrarily big numbers,
as requested. Test:
<pre>
scala> BigInt(2) to BigInt(30) filter (_ isProbablePrime 10) map (p => (p, BigInt(2).pow(p.toInt) - 1)) foreach {
| case (prime, n) => println("2**"+prime+"-1 = "+n+", with factors: "+new PrimeFactors(n).mkString(", "))
| }
2**2-1 = 3, with factors: 3
2**3-1 = 7, with factors: 7
2**5-1 = 31, with factors: 31
2**7-1 = 127, with factors: 127
2**11-1 = 2047, with factors: 23, 89
2**13-1 = 8191, with factors: 8191
2**17-1 = 131071, with factors: 131071
2**19-1 = 524287, with factors: 524287
2**23-1 = 8388607, with factors: 47, 178481
2**29-1 = 536870911, with factors: 233, 1103, 2089
</pre>
=={{header|Slate}}==
| |||