Prime decomposition: Difference between revisions
Content deleted Content added
→{{header|Python}}: performance hints |
Added Scala |
||
Line 1,049: | Line 1,049: | ||
47 : 140737488355327 : [2351, 4513, 13264529] |
47 : 140737488355327 : [2351, 4513, 13264529] |
||
53 : 9007199254740991 : [6361, 69431, 20394401]</pre> |
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}}== |
=={{header|Slate}}== |