Commits

Martin Klinke  committed ea2ebe3

several more problems (Problem35 is not done yet)

  • Participants
  • Parent commits fd31d0a

Comments (0)

Files changed (3)

File src/com/mklinke/euler/Problem32.scala

+package com.mklinke.euler
+
+object Problem32 {
+  def main(args: Array[String]) {
+     
+  }
+}

File src/com/mklinke/euler/Problem33.scala

+package com.mklinke.euler
+
+class Rational(n: Int, d: Int) {
+  private def gcd(x: Int, y: Int): Int =
+    {
+      if (x == 0) y
+      else if (x < 0) gcd(-x, y)
+      else if (y < 0) -gcd(x, -y)
+      else gcd(y % x, x)
+    }
+  private val g = gcd(n, d)
+
+  val numer: Int = n // /g
+  val denom: Int = d // /g
+
+  def +(that: Rational) =
+    new Rational(numer * that.denom + that.numer * denom, denom * that.denom)
+  def -(that: Rational) =
+    new Rational(numer * that.denom - that.numer * denom, denom * that.denom)
+  def *(that: Rational) =
+    new Rational(numer * that.numer, denom * that.denom)
+  def /(that: Rational) =
+    new Rational(numer * that.denom, denom * that.numer)
+
+  def simplify() =
+    new Rational(numer / g, denom / g)
+
+  override def toString() =
+    "Rational: [" + numer + " / " + denom + "]"
+}
+
+object Problem33 {
+
+  def check(rat: Rational) = {
+    val numerChars = rat.numer.toString().toCharArray()
+    val denomChars = rat.denom.toString().toCharArray()
+    val commonChars = numerChars.filter(char => denomChars.
+      filter(char2 => char == char2).length > 0)
+    if (commonChars.length == 1 && commonChars(0) != '0') {
+      val simpleNumerChars = numerChars.filter(c => c != commonChars(0))
+      val simpleDenomChars = denomChars.filter(c => c != commonChars(0))
+      if (simpleNumerChars.length > 0 && simpleDenomChars.length > 0) {
+        val source = rat.simplify
+        val target = new Rational(simpleNumerChars(0) - 48,
+          simpleDenomChars(0) - 48).simplify
+        val equal = source.numer == target.numer && source.denom == target.denom
+        if (equal)
+          Console println rat
+        equal
+      }
+    }
+    false
+  }
+
+  def main(args: Array[String]) {
+
+    var result = (1 to 99).map(num =>
+      num to 99 map (denom => new Rational(num, denom)) filter (rational => check(rational)))
+
+     val product = result.map(entry => if(entry.length > 0) entry.reduceLeft(_*_) else new Rational(1,1)).reduceLeft(_*_)
+     
+     Console println product
+     
+    //REMARK: No beautiful solution... how can the list be flattened?
+    Console print (new Rational(16, 64) * new Rational(19, 95) * new Rational(26, 65) * new Rational(49, 98)).simplify
+
+  }
+}

File src/com/mklinke/euler/Problem35.scala

+package com.mklinke.euler
+
+object Problem35 {
+ def main(args : Array[String]) {
+
+    for (n <- 1 to 1000000; if (smallestDivisor(n) == n)) {
+
+      val d = smallestDivisor(n)
+      println(n + " prime!" )
+    }
+  }
+
+  def isPrime(n : Int) : Boolean = {
+
+    n == smallestDivisor(n)
+  }
+
+  def smallestDivisor(n : Int) : Int = {
+
+    findDivisor(n, 2)
+  }
+
+  def findDivisor(n : Int, testDivisor : Int) : Int = {
+
+    if (square(testDivisor) > n)
+      n
+    else if (divides(testDivisor, n))
+      testDivisor
+    else
+      findDivisor(n, testDivisor + 1)
+  }
+
+  def square(n : Int) : Int = {
+
+    n * n
+  }
+
+  def divides(d : Int, n : Int) : Boolean = {
+
+    (n % d) == 0
+  }
+}