# Euler Solution 187

### From ProgSoc Wiki

# 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