# Euler Solution 87

### From ProgSoc Wiki

(Difference between revisions)

(→Solutions for Problem 87) |
|||

Line 43: | Line 43: | ||

{- Return the length of all the numbers -} | {- Return the length of all the numbers -} | ||

main = print (length (toLim 50000000 p2 p3 p4)) | main = print (length (toLim 50000000 p2 p3 p4)) | ||

+ | |||

+ | == Python by Althalus == | ||

+ | Time: 2.5 seconds | ||

+ | |||

+ | from primeFunctions import genPrimes | ||

+ | |||

+ | # Always with the primes | ||

+ | primes = genPrimes(7072) | ||

+ | # prime squares | ||

+ | primes2 = map(lambda x: x**2, primes) | ||

+ | # prime cubes | ||

+ | primes3 = map(lambda x: x**3, primes) | ||

+ | # prime to the four | ||

+ | primes4 = map(lambda x: x**4, primes) | ||

+ | results = {} | ||

+ | |||

+ | # Add, add, add | ||

+ | for x in primes2: | ||

+ | for y in primes3: | ||

+ | if x+y > 50000000: | ||

+ | break | ||

+ | for z in primes4: | ||

+ | res = x+y+z | ||

+ | if res > 50000000: | ||

+ | break | ||

+ | results[res] = 1 | ||

+ | |||

+ | |||

+ | print len(results) | ||

[[Category: Euler]] | [[Category: Euler]] |

## Latest revision as of 01:31, 22 July 2011

# Solutions for Problem 87

Find the number of numbers below 50 million that can be written as the sum of a prime squared, a prime cubed and a prime to the four.

## Haskell by SanguineV

Runtime: 72 seconds

{- Primes as usual -} primes :: [Integer] primes = 2:3:primes' where 1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]] primes' = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes' divides n p = mod n p == 0 {- Predefine the primes squared, cubed, etc. -} p2 = map (\x -> x * x) primes p3 = map (\x -> x * x * x) primes p4 = map (\x -> x * x * x * x) primes {- Merge two sorted lists of integers removing duplicates -} merge :: [Integer] -> [Integer] -> [Integer] merge [] bbs = bbs merge aas [] = aas merge aas@(a:as) bbs@(b:bs) = case compare a b of LT -> a : merge as bbs EQ -> a : merge as bs GT -> b : merge aas bs {- Return all the numbers that can be expressed as a prime squared + prime - cubed + a prime t the four. -} toLim :: Integer -> [Integer] -> [Integer] -> [Integer] -> [Integer] toLim lim (a:as) (b:bs) (c:cs) | a + b + c >= lim = [] toLim lim (a:as) bbs ccs = merge (inner (map (\x -> a + x) bbs) ccs) (toLim lim as bbs ccs) where inner :: [Integer] -> [Integer] -> [Integer] inner (b:bs) (c:cs) | b + c >= lim = [] inner (b:bs) cs = merge (takeWhile (< lim) (map (\x -> x + b) cs)) (inner bs cs) {- Return the length of all the numbers -} main = print (length (toLim 50000000 p2 p3 p4))

## Python by Althalus

Time: 2.5 seconds

from primeFunctions import genPrimes # Always with the primes primes = genPrimes(7072) # prime squares primes2 = map(lambda x: x**2, primes) # prime cubes primes3 = map(lambda x: x**3, primes) # prime to the four primes4 = map(lambda x: x**4, primes) results = {} # Add, add, add for x in primes2: for y in primes3: if x+y > 50000000: break for z in primes4: res = x+y+z if res > 50000000: break results[res] = 1 print len(results)