Rust Implementation of Problem 187
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0187::p0187() -> utils::Answer
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*/
25use std::collections::HashSet;
26
27use crate::include::primes::primes_until;
28use crate::include::utils::Answer;
29
30pub fn p0187() -> Answer {
31 let ten_8: u64 = 10_u64.pow(8);
32 let cached_primes: Vec<u64> = primes_until::<u64>(ten_8 / 2 + 1).collect();
33 let mut seen: HashSet<u64> = HashSet::new();
34 for &y in cached_primes.iter() {
35 for &x in cached_primes.iter() {
36 if x > ten_8 / y {
37 break;
38 }
39 seen.insert(x * y);
40 }
41 }
42 return Answer::Int((seen.len() as u64).into());
43}