So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.
Project Euler’s Problem #4 statement is —
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.
And here’s the solution.
def int_to_list(number):
return map(int, str(number))
def is_palindrome(number):
local_list = int_to_list(number)
return local_list == list(reversed(local_list))
pal = 0
if __name__ == "__main__":
for i in range(100,1000):
for j in range(100,1000):
if is_palindrome(i * j):
print "%d * %d = %d"%(i, j, i*j)
if i * j > pal:
pal = i * j
print pal
So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.
Project Euler’s Problem #3 statement is —
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
My solution is really ugly and is basically dumb-, brute-force.
So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.
Project Euler’s Problem #8 statement is —
Find the greatest product of five consecutive digits in the 1000-digit number.
So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.
Project Euler’s Problem #7 statement is —
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
It’s a straightforward problem to solve using brute force, but I went with a mixed approach doing some math instead.
I initially used a dumb brute-force which ended up running fast enough. But reading about primes, I came across this property by which if a number cannot be divided by any number smaller than sqrt(n), it is a prime. That required significantly less tests to be performed inside is_prime, but then again, it had to perform a square root calculation for every number we need to test. In the end, the algorithm above performed slightly better (0.02s to be exact.)
Updated: Thanks to Eduardo Habkost for pointing out the fact that I had mistakenly pasted the wrong version of the script. I fixed the text to reflect that.