Python Implementation of Problem 187
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 187
I was able to chain this with a previous problem. Probably a suboptimal solution because of it, but it felt prettier this way.
I was able to add a short-circuited fail case to the is_prime() method, though
Revision 1:
Switched to a set comprehension with caching. This means that I can remove it from the slow list.
Problem:
A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.
There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
How many composite integers, n < 10**8, have precisely two, not necessarily distinct, prime factors?
1"""
2Project Euler Problem 187
3
4I was able to chain this with a previous problem. Probably a suboptimal
5solution because of it, but it felt prettier this way.
6
7I was able to add a short-circuited fail case to the is_prime() method, though
8
9Revision 1:
10
11Switched to a set comprehension with caching. This means that I can remove it
12from the slow list.
13
14Problem:
15
16A composite is a number containing at least two prime factors. For example,
1715 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.
18
19There are ten composites below thirty containing precisely two, not necessarily
20distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
21
22How many composite integers, n < 10**8, have precisely two, not necessarily
23distinct, prime factors?
24"""
25from itertools import takewhile
26
27from .lib.primes import primes
28
29
30def main() -> int:
31 ten_8 = 10**8
32 cached_primes = tuple(primes(ten_8 // 2 + 1))
33 seen = {
34 x * y
35 for y in cached_primes
36 for x in takewhile((ten_8 // y).__ge__, cached_primes)
37 }
38 return len(seen)