Euler Solution 187

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Solutions for Problem 187)
 
Line 26: Line 26:
  {- Print the number of cross products of primes less than the limit -}
  {- Print the number of cross products of primes less than the limit -}
  main = print (prod 100000000 primes)
  main = print (prod 100000000 primes)
 +
 +
== Python by Althalus ==
 +
 +
Runtime: 38 seconds
 +
 +
import psyco
 +
psyco.full()
 +
 +
limit = 10**8
 +
primes = genPrimes(limit / 2)
 +
 +
# Exploiting semiprimes.
 +
res = 0
 +
for x in primes:
 +
    for y in primes:
 +
        if x * y < limit:
 +
            if y >= x:
 +
                res += 1
 +
        else: break
 +
print res
 +
[[Category: Euler]]
[[Category: Euler]]

Latest revision as of 04:33, 12 April 2012

Solutions for Problem 187

Find all the numbers less than 100000000 that have exactly 2 primes as their factors.

Haskell by SanguineV

Runtime: 740 seconds!!

{- Prime numbers 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     = n `mod` p == 0

{- Do the cross product of a list, counting the number of elements less than some limit -}
prod :: Integer -> [Integer] -> Int
prod lim ls = inner ls
  where
    inner :: [Integer] -> Int
    inner (x:xs) | x * x > lim = 0
    inner (x:xs) = 1 + (length (takeWhile (<= div lim x) xs)) + (inner xs)

{- Print the number of cross products of primes less than the limit -}
main = print (prod 100000000 primes)

Python by Althalus

Runtime: 38 seconds

import psyco
psyco.full()

limit = 10**8
primes = genPrimes(limit / 2)

# Exploiting semiprimes.
res = 0
for x in primes:
    for y in primes:
        if x * y < limit:
            if y >= x:
                res += 1
        else: break
print res
Personal tools