#!/usr/local/bin/perl $fib1 = 1; $fib2 = 2; $sum = 1; while ($fib2 < 4000000) { if($fib2 % 2 == 0){ $sum += $fib2; } $aux = $fib2; $fib2 += $fib1; $fib1 = $aux; } print $sum;
Sunday, February 23, 2014
Perl solution to Project Euler's problem #2
http://projecteuler.net/problem=2
Perl solution to Project Euler's problem #1
#!/usr/local/bin/perl $sum = 0; for $i (1 .. 999) { if(($i % 3) == 0){ $sum += $i; } else { if(($i % 5) == 0){ $sum += $i; } } } print $sum;
https://ideone.com/5NrFot
Tuesday, December 3, 2013
Python solution to Project Euler problem number 5
Solution
def is_prime(x, primes): for p in primes: if x % p == 0: return False return True assert is_prime(3, [2]) assert not is_prime(4, [2, 3]) def smallest_common_multiple_of_all_numbers_up_to(x): if x == 1: return 1 y = 1 primes = [] for i in range(2, x + 1): if is_prime(i, primes): primes.append(i) y *= i continue if y % i == 0: continue for p in primes: if (y * p) % i == 0: y *= p break return y assert smallest_common_multiple_of_all_numbers_up_to(3) == 6 assert smallest_common_multiple_of_all_numbers_up_to(10) == 2520 print smallest_common_multiple_of_all_numbers_up_to(20)
Sunday, December 1, 2013
Solution to Project Euler problem number 4 in Python
Solution
def reverse(number): result = 0 while number > 0: result = result * 10 + (number % 10) number = int(number / 10) return result def is_palindrome(number): return number == reverse(number) largestPalindrome = 0 a = 999 while a >= 100: if a % 11 == 0: b = 999 db = 1 else: b = 990 db = 11 while b >= a: if a*b <= largestPalindrome: break if is_palindrome(a*b): largestPalindrome = a*b b = b-db a = a-1 print largestPalindrome
Monday, November 25, 2013
Solution for Project Euler's problem number 6 in Python
Problem 6 - Sum square difference
The sum of the squares of the first ten natural numbers is,1 ** 2 + 2 ** 2 + ... + 10 ** 2 = 385The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10) ** 2 = 552 = 3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Solution
its time complexity is O(n) (linear)
it's under a second for 10,000 but it takes a while for 100,000def sum(an): n = int(an / 2) return n * (1 + an) def sum_square(an): sum = 0 for i in range(1, an + 1): sum += i ** 2 return sum def problem6(an): return sum(an) ** 2 - sum_square(an) print problem6(100)
Sunday, November 24, 2013
Solution for Project Euler's problem number 3 in Python
Problem 3 - Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?Simplest solution
its time complexity is O(n) (linear) with the largest factor
It means it's fast for 600851475143 but not for 600851475145def get_prime_factors(number): factor=2 while number <> 1 & factor <= number: factor += 1 while number % factor == 0: yield factor number /= factor for x in get_prime_factors(600851475143): print x
Fastest solution
its time complexity is O(sqrt(n)) (fractional power) with the largest factor.
def get_prime_factors(number): while number % 2 == 0: yield 2 number /= 2 factor=1 maxFactor = int(number ** .5) while number <> 1 & factor <= maxFactor: factor += 2 while number % factor == 0: yield factor number /= factor if number > 1: yield number for x in get_prime_factors(600851475145): print x
Solution in Python for Project Euler's problem #2
Problem 2 - Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Python solution
it is very fast even for numbers up to 1e200
def fibsum(maximum): fib1 = 0 fib2 = 1 sum = 0 while fib2 < maximum: aux = fib2 fib2 += fib1 fib1 = aux if fib2 & 1 == 0: sum += fib2 return sum print fibsum(int(4e6))
Subscribe to:
Posts (Atom)