Statistics

Problem Statement for "PrimeSequences"

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).

Given ints 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.

Definition

Class:
PrimeSequences
Method:
getLargestGenerator
Parameters:
int, int
Returns:
int
Method signature:
int getLargestGenerator(int N, int D)
(be sure your method is public)

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

  1. 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.

  2. 42

    3

    Returns: 23

    The optimal sequence is {23, 11, 5, 2}, which has length 4.

  3. 666

    7

    Returns: -1

    Six hundred and sixty six is, apparently, not large enough to contain a sequence of length 7.

  4. 1337

    5

    Returns: 47

  5. 100000

    5

    Returns: 2879

    There are not many sequences of length five or more.

  6. 40000

    1

    Returns: 39989

    39989 is the largest prime number less than or equal to 40000.

  7. 18

    3

    Returns: 11

  8. 18

    1

    Returns: 17

  9. 18

    5

    Returns: -1

  10. 10

    2

    Returns: 7

  11. 42

    4

    Returns: 23

  12. 42

    2

    Returns: 23

  13. 42

    6

    Returns: -1

  14. 1337

    5

    Returns: 47

  15. 1337

    1

    Returns: 1327

  16. 1337

    2

    Returns: 1319

  17. 100000

    6

    Returns: 2879

  18. 100000

    2

    Returns: 99839

  19. 100000

    4

    Returns: 96959

  20. 100000

    8

    Returns: -1

  21. 1000000

    6

    Returns: 2879

  22. 1000000

    2

    Returns: 999959

  23. 1000000

    8

    Returns: -1

  24. 10000000

    6

    Returns: 4068479

  25. 10000000

    2

    Returns: 9999047

  26. 666

    5

    Returns: 47

  27. 666

    4

    Returns: 47

  28. 666

    1

    Returns: 661

  29. 1234

    5

    Returns: 47

  30. 1234

    2

    Returns: 1187

  31. 1234

    8

    Returns: -1

  32. 345345

    6

    Returns: 2879

  33. 345345

    2

    Returns: 344843

  34. 345345

    1

    Returns: 345329

  35. 345345

    8

    Returns: -1

  36. 64231

    6

    Returns: 2879

  37. 64231

    9

    Returns: -1

  38. 9348543

    6

    Returns: 4068479

  39. 9348543

    4

    Returns: 9256799

  40. 9348543

    3

    Returns: 9347879

  41. 2

    1

    Returns: 2

  42. 2

    3

    Returns: -1

  43. 3

    1

    Returns: 3

  44. 3

    4

    Returns: -1

  45. 19

    3

    Returns: 11

  46. 19

    2

    Returns: 11

  47. 22

    3

    Returns: 11

  48. 22

    1

    Returns: 19

  49. 22

    2

    Returns: 11

  50. 22

    5

    Returns: -1

  51. 24

    4

    Returns: 23

  52. 24

    2

    Returns: 23

  53. 177

    5

    Returns: 47

  54. 177

    3

    Returns: 167

  55. 199

    5

    Returns: 47

  56. 199

    2

    Returns: 179

  57. 199

    1

    Returns: 199

  58. 199

    7

    Returns: -1

  59. 2879

    6

    Returns: 2879

  60. 2879

    2

    Returns: 2879

  61. 2878

    5

    Returns: 1439

  62. 2878

    4

    Returns: 1439

  63. 2878

    7

    Returns: -1

  64. 2880

    6

    Returns: 2879

  65. 2880

    2

    Returns: 2879

  66. 2880

    5

    Returns: 2879

  67. 424242

    6

    Returns: 2879

  68. 424242

    2

    Returns: 424199

  69. 435566

    6

    Returns: 2879

  70. 435566

    5

    Returns: 2879

  71. 435566

    9

    Returns: -1

  72. 1234567

    6

    Returns: 2879

  73. 1234567

    5

    Returns: 1067999

  74. 9511197

    5

    Returns: 8624159

  75. 9428099

    4

    Returns: 9256799

  76. 9101919

    4

    Returns: 9063599

  77. 8970000

    4

    Returns: 8877119

  78. 9050699

    5

    Returns: 8624159

  79. 10000000

    10

    Returns: -1

  80. 9

    3

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: