1. Martin Klinke
  2. ScalaEuler

Source

ScalaEuler / src / com / mklinke / euler / Problem37.scala

/**
 * *
 *  Copyright 2012 Martin Klinke, http://www.martinklinke.com.
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package com.mklinke.euler

/**
 * @author Martin Klinke
 *
 */
object Problem37 {
  def main(args: Array[String]) {
    val start = System.currentTimeMillis;
    println("Sum of truncatable primes: " + sumTruncatablePrimes(10, 0, 0))
    println("Duration: " + (System.currentTimeMillis - start) + " ms");
  }

  def sumTruncatablePrimes(currentN: Int, count: Int, currentSum: Int): Int = {
    if (count == 11)
      currentSum
    else {
      val foundMatch = isTruncatablePrime(currentN)
      sumTruncatablePrimes(currentN + 1, if (foundMatch) count + 1 else count, if (foundMatch) currentSum + currentN else currentSum)
    }
  }

  def isTruncatablePrime(n: Int): Boolean = {
    isLeftTruncatablePrime(n) && isRightTruncatablePrime(n)
  }

  def isLeftTruncatablePrime(n: Int): Boolean = {
    val digits = n.toString.toList
    if (digits.length == 1)
      isPrime(digits.head - 48)
    else
      isPrime(n) && isLeftTruncatablePrime(digits.tail.map(c => c - 48).mkString.toInt)
  }

  def isRightTruncatablePrime(n: Int): Boolean = {
    val digits = n.toString.toList
    if (digits.length == 1)
      isPrime(digits.head - 48)
    else
      isPrime(n) && isRightTruncatablePrime(digits.reverse.tail.reverse.map(c => c - 48).mkString.toInt)
  }

  def isPrime(n: Int): Boolean = {
    if (n == 1)
      false
    else
      n == smallestDivisor(n)
  }

  def smallestDivisor(n: Int): Int = {
    findDivisor(n, 2)
  }

  def findDivisor(n: Int, testDivisor: Int): Int = {
    if (testDivisor * testDivisor > n)
      n
    else if (n % testDivisor == 0)
      testDivisor
    else
      findDivisor(n, testDivisor + 1)
  }
}