EratosthenSieve2
SRM 296 · 2006-04-03 · by Mike Mirzayanov
Problem Statement
Let N1 = {1, 2, 3, 4, 5, ..., 1000} (the set of all positive integers between 1 and 1000, inclusive).
Delete every second number in N1. The result is N2 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ..., 999}.
Delete every third number in N2. The result is N3 = {1, 3, 7, 9, 13, 15, 19, 21, 25, ..., 999}.
Delete every fourth number in N3. The result is N4 = {1, 3, 7, 13, 15, 19, 25, 27, ...}.
...
Delete every tenth number in N9. The result is N10. Find and return the n-th element of sequence N10, where n is a 1-based index.
Notes
- N10 will contain exactly 101 elements.
Constraints
- n will be between 1 and 100, inclusive.
3 Returns: 7
1 Returns: 1
10 Returns: 79
25 Returns: 223
4 Returns: 13
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EratosthenSieve2 with a public method int nthElement(int n) · 106 test cases · 2 s / 256 MB per case