Euler Solution 87

From ProgSoc Wiki

Jump to: navigation, search

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)
Personal tools