# Euler Solution 187

### From ProgSoc Wiki

(Difference between revisions)

(→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