PreprimeNumbers
SRM 307 · 2006-06-14 · by Mike Mirzayanov
SRM 307 · 2006-06-14 · by Mike Mirzayanov · Search, Simple Math
Problem Statement
Problem Statement
A number is preprime if it has exactly 4 positive integer divisors. For example, 6 is preprime because its divisors are 1, 2, 3, and 6. The integers 6, 8, 10, 14 form the beginning of an infinite sequence of preprime numbers. Find the n-th element of this sequence, where n is a 1-based index.
Constraints
- n will be between 1 and 1000000, inclusive.
Examples
0)
2 Returns: 8
The beginning of an infinite sequence of preprime numbers is: 6, 8, 10, 14, ... The second number is 8.
1)
4 Returns: 14
The beginning of an infinite sequence of preprime numbers is: 6, 8, 10, 14, ... The fourth number is 14.
2)
24 Returns: 77
3)
43765 Returns: 193539
4)
1 Returns: 6
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PreprimeNumbers with a public method int nthNumber(int n) · 78 test cases · 2 s / 256 MB per case