Problem:
Calculate the sum of all the primes below two million (2000000)
import scala.collection.mutable.ListBuffer
import scala.collection.mutable.Map
object Problem10 {
def main(args: Array[String]) :Unit = {
println(findSumOfPrimesFast(2000000))
}
def findSumOfPrimesFast(max: Int) : BigInt = {
//initialize sum to basic primes
var sum = BigInt(0)
if(max > 2) sum += 2
if(max > 3) sum += 3
if(max > 5) sum += 5
if(max > 7) sum += 7
if(max > 11) sum += 11
//initialize map with numbers < max and not multiples of basic primes
var map = Map[Int, Boolean]()
for {
i <- 2.until(max)
if(i % 2 != 0)
if(i % 3 != 0)
if(i % 5 != 0)
if(i % 7 != 0)
if(i % 11 != 0)
} map += (i -> true)
var i = 13
while(i <= Math.sqrt(max)) {
if(map.contains(i)) {
map -- multiples(i, max)
sum += i
}
i += 2 //skipping evens
}
//all numbers greater than sqrt(max) are primes
val iter = map.keys
while(iter.hasNext) {
sum += iter.next
}
return sum
}
def multiples(number:Int, max:Int) : Iterable[Int] = {
val numbers = new ListBuffer[Int]()
var multiple = number
var loop = 1;
while(multiple < max) {
numbers += multiple
loop += 1
multiple = number * loop
}
return numbers
}
}
scala
Problem:
Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.
object Problem9 {
def main(args: Array[String]) :Unit = {
val list = findPythagoreanTriplets(1000)
val product = list.first._1 * list.first._2 * list.first._3
println(product)
}
def findPythagoreanTriplets(number:Int) : List[Tuple3[Int, Int, Int]] = {
for{ a <- 1.to(number - 1)
b <- (a+1).to(number)
c = number - a - b
if(a*a + b*b == c*c)
} return List((a,b,c))
return List()
}
}
scala
Problem:
Discover the largest product of five consecutive digits in the 1000-digit number.
object Problem8 {
def main(args: Array[String]) :Unit = {
println(solve(numberStr))
}
val numberStr = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
def solve(number:String) : Int = {
val number1 = number
val number2 = number1.substring(1);
val number3 = number2.substring(1);
val number4 = number3.substring(1);
val number5 = number4.substring(1);
var max = 0
var i = 0
while(i < numberStr.length - 5)
{
val n1 = Integer.parseInt(number1(i).toString)
val n2 = Integer.parseInt(number2(i).toString)
val n3 = Integer.parseInt(number3(i).toString)
val n4 = Integer.parseInt(number4(i).toString)
val n5 = Integer.parseInt(number5(i).toString)
val product = n1 * n2 * n3 * n4 * n5
if(product == Math.pow(9, 5)) return product
if(product > max) {
println(n1 + "," + n2 + "," + n3 + "," + n4 + "," + n5)
max = product
}
i += 1
}
return max
}
}
scala
scala
Problem:
Find the 10001st prime.
object Problem7 {
def main(args: Array[String]) :Unit = {
println(findNthPrime(10001))
}
def findNthPrime(n:Int) : Long = {
var primeSet = List[Long](2L)
var number = 3L
while(primeSet.size < n)
{
if(isPrime(primeSet, number)) primeSet = number :: primeSet
number += 1
}
return primeSet.first
}
def isPrime(primeSet:Seq[Long], n:Long) : Boolean = {
for( i <- primeSet ) {
if(n % i == 0) return false
}
return true
}
}
scala
scala
Problem:
What is the difference between the sum of the squares and the square of the sums?
object Problem6 {
def main(args: Array[String]) :Unit = {
println(solve(100))
}
def solve(number:Int) : Int = {
var sum = 0
for {
i <- 1.to(number-1)
j <- (i+1).to(number)
} sum += 2 * i * j
return sum
}
}
scala
scala
Problem:
What is the smallest number divisible by each of the numbers 1 to 20?
object Problem5 {
def main(args : Array[String]) : Unit = {
println(solve(20))
}
def solve(number:Int) : Long = {
var lcm = 1L
for( i <- 2.to(number); if(isPrime(i))) {
val multiplesOfI = countPowersOfN(i, number)
lcm *= power(i, multiplesOfI)
}
return lcm
}
def power(n:Int, m:Int) : Long = {
var pow = 1
for( i <- 1.to(m)) pow = pow * n
return pow
}
def isPrime(number:Int) : Boolean = {
for {
n <- 2.to(Math.sqrt(number))
} if (number % n == 0) return false
return true
}
def countPowersOfN(n:Int, number:Int) : Int = {
if(n < 2) throw new IllegalArgumentException("n should be >= 2")
if(number < n) return 0
return 1 + countPowersOfN(n, number/n)
}
}
scala
scala
Problem
Find the largest palindrome made from the product of two 3-digit numbers.
object Problem4 {
def main(args : Array[String]) : Unit = {
println(solve(3))
}
def solve(nDigits:Int) : Int = {
val start = Math.pow(10, nDigits).intValue - 1
val end = Math.pow(10, nDigits-1).intValue - 1
val nDigitNumbers = new Range(start, end, -1)
val productPalindromes = for{
n1 <- nDigitNumbers
n2 <- nDigitNumbers
prod = (n1 * n2)
if(isPalindrome(prod))
} yield prod
productPalindromes.reduceLeft(max(_,_))
}
def max(x:Int, y:Int) : Int = if(x > y) x else y
def isPalindrome(x:Int) : Boolean = {
val str = x.toString()
str == str.reverse.toString()
}
}
scala
scala
Problem:
Find the largest prime factor of a composite number.
def main(args : Array[String]) : Unit = {
println(maxPrimeFactor(BigInt("600851475143")))
}
def maxPrimeFactor(number:BigInt) : BigInt = {
var max = BigInt(1)
var lowDivisor = BigInt(1)
var highDivisor = number
while(highDivisor >= lowDivisor) {
if(number % highDivisor == 0)
if(highDivisor.isProbablePrime(10)) return maxBigInt(max, highDivisor)
else if(lowDivisor.isProbablePrime(10)) max = maxBigInt(max, lowDivisor)
lowDivisor += 1
highDivisor = number/lowDivisor
}
if(max > 1) max else number
}
def maxBigInt(x:BigInt, y:BigInt) = if(x > y) x else y
scala
scala
Problem 2:
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
object Problem2 {
def main(args : Array[String]) : Unit = {
val max = 4000000
val sum = sumOfFibNumbers(max, isEven, 0, 1, 0)
println(sum)
}
def isEven(x:Int) : Boolean = x % 2 == 0
def sumOfFibNumbers(max:Int, p:(Int => Boolean), n1:Int, n2:Int, sum:Int): Int = {
if(n1 < max) {
if(p(n1)) sumOfFibNumbers(max, p, n2, n1+n2, sum + n1)
else sumOfFibNumbers(max, p, n2, n1+n2, sum)
}
else sum
}
}
scala
scala
I have been learning Scala since couple of months, but every time i get pulled away from the learning phase it took me some time to get back into context. So this time wanted to work on some code in Scala instead of learning (I know I should have done this since the start …). I recently came to know about Project Euler (http://projecteuler.net) which I can say is excellent set of problems to solve when learning the syntax and semantics of a language. So I wanted to document my progress in a series of posts starting this one. Any kind of feedback is appreciated.
Problem 1:
Add all the natural numbers below one thousand that are multiples of 3 or 5.
object Problem1 {
def main(args : Array[String]) : Unit = {
val sum = 1.until(1000)
.filter(x => (x % 3 == 0 || x % 5 == 0))
.reduceLeft(_+_)
println(sum)
}
}
scala
scala