Underprimes
SRM 442 · 2009-06-13 · by mateuszek
Problem Statement
The prime factorization of a number X is the list of prime numbers that multiply together to form X. For example, the prime factorization of 12 is 2 * 2 * 3. Note that 1 is not a prime number.
An underprime is a number whose prime factorization contains a prime number of elements. For example, 12 is an underprime because its prime factorization contains 3 elements, and 3 is a prime number. Given
Notes
- A positive integer number is called prime if it has exactly two divisors - 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, and 4, 6, 8 and 9 are not prime. By convention, 1 is not considered to be a prime number.
- All prime factorizations of the same integer always contain the same prime numbers and can only differ by the order of primes within them.
Constraints
- A will be between 2 and 100000, inclusive.
- B will be between A and 100000, inclusive.
2 10 Returns: 5
The underprimes in this interval are: 4, 6, 8, 9, 10.
100 105 Returns: 2
The underprimes in this interval are 102 = 2 * 3 * 17 and 105 = 3 * 5 * 7.
17 17 Returns: 0
17 is a prime number, so its prime factorization contains one element. 1 is not a prime, so 17 is not an underprime.
312 12839 Returns: 7987
123 456 Returns: 217
Submissions are judged against all 49 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Underprimes with a public method int howMany(int A, int B) · 49 test cases · 2 s / 256 MB per case