Skip to content

Instantly share code, notes, and snippets.

@thatwist
Created December 6, 2017 18:41
Show Gist options
  • Save thatwist/2a26ddc7b609f98d3d8c638eb82c96d9 to your computer and use it in GitHub Desktop.
Save thatwist/2a26ddc7b609f98d3d8c638eb82c96d9 to your computer and use it in GitHub Desktop.
Finds biggest palindrome which is a product of two prime numbers
import scala.annotation.tailrec
import scala.collection.parallel.mutable
object Solution extends App {
def isPalindrome(n: Int): Boolean = {
var num = n
//reversing number
var rev = 0
var rmd = 0
while(num > 0) {
rmd = num % 10;
rev = rev * 10 + rmd;
num = num / 10;
}
rev == n
}
def sieveOfEratosthenes(limit: Int): mutable.ParSet[Int] = {
val (primes: mutable.ParSet[Int], sqrtLimit) =
(mutable.ParSet.empty ++ (2 to limit), math.sqrt(limit).toInt)
@tailrec
def prim(candidate: Int): Unit = {
if (candidate <= sqrtLimit) {
if (primes contains candidate)
primes --= candidate * candidate to limit by candidate
prim(candidate + 1)
}
}
prim(2)
primes
}
// filtering only 5-digit numbers
val sieved = sieveOfEratosthenes(99999).filter(_ > 10000)
// (MaxProduct, PairOfNumbers)
val foldZero: (Int, (Int, Int)) = (0, (0, 0))
val result = sieved.toList.tails.foldLeft(foldZero) {
case (outer, Nil) => outer
case (outer, h :: tail) =>
val innerResult = tail.foldLeft(foldZero) {
case (innerFold@(max, maxPair), t) =>
val product = h * t
if (isPalindrome(product) && product > max) {
product -> Tuple2(h, t)
} else innerFold
}
// if inner fold returned bigger max then use it as a new max in outer fold
if (innerResult._1 > outer._1) innerResult else outer
}
println(result)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment