The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
Problem 10 posed an interesting issue for me. I came up with a solution I thought would work well right away, but I couldn't seem to get the correct answer. After poring over my code and playing around, I finally found my issue - my isPrime function had an error in it, causing me to be off by 2.
What is interesting about this scenario is that I've been using that same function for lots of different problems, but since the function was only broken for the number 2, it didn't matter in those. If I had some sort of test that say, verified the function against a random set of prime numbers, I would have found the issue much sooner. This speaks to how important it is to test even seemingly working things whenever you can.
Another by product of the issue is that I did a little more research on calculating prime numbers. Wikipedia had a nice article about the Sieve of Eratosthenes. This gave me a much better understanding of how it works. While I am not changing my code (yet) to use a sieve, it was certainly valuable to learn more about how its done.
Well, I did manage to finish it, and here is my solution. Enjoy:
object Problem10 { def main(args: Array[String]): Unit = { var holder : BigDecimal = new BigDecimal(new java.math.BigDecimal("0")); (2 to 1999999).filter{next => val prime = isPrime(next);if(prime){holder = holder + new java.math.BigDecimal(new Integer(next).toString())};prime} println(holder) } /** * Brute force method. Perhaps a better method * can be implemented here? */ def isPrime(number: Long) : Boolean = { if(number == 2) return true if(number%2==0 || number % 3==0) return false; val sqrt:Int = Math ceil (Math sqrt number) intValue; (true /: (3 to sqrt))((isPrime, next) => { if(number % next == 0) return false isPrime }) } }
Now that I've completed #10, I get a Euler award. I have become a 'Decathlete' for finishing 10 problems in a row.
And with that, I think I will finish blogging about my Euler solutions. I still plan on working through the problems, but I think I've worn out my Euler solution posts and will move on to some other interesting topics.
I've been working for StudybBlue for about 9 months now. If you don't know what StudyBlue is, it's a fantastic place for students to create online flashcards, study those flashcards, create quizzes from them, and track their progress. In other words, its a product that makes students more efficient and effective.
StudyBlue is more than a Web site, however. It also produces native flashcard applications for iPhone and Android to allow students to study their cards on the go. The goal for our company is to create a total user experience and we invest a lot of time, effort and energy into our application designs. Apparently, that hard work is starting to payoff.
We were recently notified that we were nominated for the the Best App Ever Awards. While its not the biggest award or the best known, the interesting thing about it is that it is a user-driven award. It means that one of our users nominated our app and other users will be voting on it. In my mind this is one of the highest compliments StudyBlue could be paid. After all, it doesn't really matter what anyone thinks but your users, and it seems that we're keeping at least some of ours pretty happy.
I've still been (slowly) working my way through the Project Euler Problems. The next one is problem 9 which reads:
A Pythagorean triplet is a set of three natural numbers, a b c, for which, a^2 + b^2 = c^2 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc.
For this problem, I didn't use anything fancy. Two for-comprehensions and basic math produced the solution in short order. The only thing to mention about this solution is that it actually finds the solution twice since I'm iterating1 to 998 twice. I considered trying to optimize this, however, it runs plenty fast. Since my goal in solving these isn't to come up with the fastest solution, but to come up with a solution that has no mutable state, I have met my goal. Therefore, I present you the solution to problem 9:
object Problem9 { def main(args: Array[String]): Unit = { for (a <- 1 to 998) { for (b <- 1 to 998) { val c = 1000 - (a + b) if ((a * a) + (b * b) == (c * c)) { println("the triplet is " + a + " " + b + " " + c) println("the product is " + (a * b * c)) } } } } }
I think that's all for this one. Problem 10 is in the hopper...
