PrimeSequences
Member SRM 471 · 2009-12-03 · by espr1t
Member SRM 471 · 2009-12-03 · by espr1t · Dynamic Programming, Simple Search, Iteration
Problem Statement
Problem Statement
Elly loves "div 2" problems! By this she means problems in which she has to divide by two.
She observes an interesting property of some prime numbers: after division by two (all divisions in this problem are rounded down, i.e., integer divisions) the new number is also prime. An example of such a prime number is 7, which after division becomes 3, which is also prime. Some numbers generate even longer sequences: {47, 23, 11, 5, 2} contains 5 consecutive prime numbers, for example.
The length of the sequence generated by a natural number K is defined as the number of times K can be divided by two before obtaining a number which is not prime. For example, the number 479 has length of only 2, because after two divisions the resulting number 119 is not prime (even though subsequent divisions produce the prime numbers 59, 29, 7 and 3).
Givenint s N and D, Elleonora wants to find a positive integer X less than or equal to N such that the length of the sequence generated by X is at least D. If more than one such number exists, she wants the largest one. If no such number exists, return -1 instead.
She observes an interesting property of some prime numbers: after division by two (all divisions in this problem are rounded down, i.e., integer divisions) the new number is also prime. An example of such a prime number is 7, which after division becomes 3, which is also prime. Some numbers generate even longer sequences: {47, 23, 11, 5, 2} contains 5 consecutive prime numbers, for example.
The length of the sequence generated by a natural number K is defined as the number of times K can be divided by two before obtaining a number which is not prime. For example, the number 479 has length of only 2, because after two divisions the resulting number 119 is not prime (even though subsequent divisions produce the prime numbers 59, 29, 7 and 3).
Given
Notes
- A prime number is a natural number greater than one with exactly two distinct natural divisors: 1 and itself.
Constraints
- N will be between 2 and 10,000,000, inclusive.
- D will be between 1 and 10, inclusive.
Examples
0)
10 2 Returns: 7
Here the optimal sequence is {7, 3}. Another sequence {5, 2} with the same length exists too, but the first one begins with a larger number.
1)
42 3 Returns: 23
The optimal sequence is {23, 11, 5, 2}, which has length 4.
2)
666 7 Returns: -1
Six hundred and sixty six is, apparently, not large enough to contain a sequence of length 7.
3)
1337 5 Returns: 47
4)
100000 5 Returns: 2879
There are not many sequences of length five or more.
5)
40000 1 Returns: 39989
39989 is the largest prime number less than or equal to 40000.
Submissions are judged against all 80 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PrimeSequences with a public method int getLargestGenerator(int N, int D) · 80 test cases · 2 s / 256 MB per case