# Euler Solution 187

(Difference between revisions)
 Revision as of 02:10, 24 May 2009 (view source)← Older edit Latest revision as of 04:33, 12 April 2012 (view source)Althalus (Talk | contribs) (→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]]

# Solutions for Problem 187

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

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
```