Statistics

Problem Statement for "PrimeWithSubstring"

Problem Statement

Jaro has a favorite number: the non-negative integer N.

Jaro would also like to have a favorite prime number. But remembering new numbers is hard. Thus, the prime number must be reasonably small and it must contain his favorite number.

Find and return any long X such that:

  • X is a prime.
  • X must have at most 12 digits.
  • When written out in base 10, the digits of X must contain the digits of N as a contiguous substring.

Definition

Class:
PrimeWithSubstring
Method:
findPrime
Parameters:
int
Returns:
long
Method signature:
long findPrime(int N)
(be sure your method is public)

Notes

  • It is guaranteed that each valid input has a solution. Any valid solution will be accepted.
  • Primes are positive integers with exactly two positive integer divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, ...
  • The numbers 0 and 1 are not primes.

Constraints

  • N will be between 0 and 10^9, inclusive.

Examples

  1. 47

    Returns: 47

    The number itself is a prime, so Jaro is in luck.

  2. 42

    Returns: 15427

    The number 15427 is prime, it is small enough, and "15427" does contain "42", so this is a valid answer. Note that, for example, 4021 is not a valid answer: it is a small prime, but "4021" does not contain "42".

  3. 0

    Returns: 4021

    Now 4021 is a perfectly acceptable answer.

  4. 123456789

    Returns: 312345678971

    Watch out for integer overflow, the answers are sometimes too big for a 32-bit data type.

  5. 111

    Returns: 2111

  6. 999959782

    Returns: 999959782181

  7. 1

    Returns: 11

  8. 2

    Returns: 2

  9. 3

    Returns: 3

  10. 4

    Returns: 41

  11. 5

    Returns: 5

  12. 6

    Returns: 61

  13. 7

    Returns: 7

  14. 8

    Returns: 83

  15. 9

    Returns: 97

  16. 10

    Returns: 101

  17. 11

    Returns: 11

  18. 12

    Returns: 127

  19. 13

    Returns: 13

  20. 14

    Returns: 149

  21. 15

    Returns: 151

  22. 16

    Returns: 163

  23. 17

    Returns: 17

  24. 18

    Returns: 181

  25. 19

    Returns: 19

  26. 20

    Returns: 2003

  27. 23

    Returns: 23

  28. 24

    Returns: 241

  29. 55

    Returns: 557

  30. 60

    Returns: 601

  31. 98

    Returns: 983

  32. 99

    Returns: 991

  33. 162

    Returns: 1621

  34. 186

    Returns: 1861

  35. 200

    Returns: 2003

  36. 220

    Returns: 2203

  37. 426

    Returns: 4261

  38. 596

    Returns: 59611

  39. 777

    Returns: 77711

  40. 993

    Returns: 9931

  41. 1285

    Returns: 12853

  42. 1732

    Returns: 17321

  43. 1988

    Returns: 19889

  44. 2192

    Returns: 21929

  45. 3021

    Returns: 30211

  46. 5318

    Returns: 53189

  47. 5905

    Returns: 59051

  48. 7000

    Returns: 70001

  49. 7777

    Returns: 77773

  50. 11111

    Returns: 111119

  51. 30398

    Returns: 303983

  52. 34942

    Returns: 349423

  53. 35396

    Returns: 353963

  54. 90000

    Returns: 900001

  55. 129158

    Returns: 12915803

  56. 179310

    Returns: 1793101

  57. 270108

    Returns: 27010817

  58. 389047

    Returns: 389047

  59. 485223

    Returns: 48522337

  60. 777777

    Returns: 77777719

  61. 800000

    Returns: 8000009

  62. 851660

    Returns: 85166009

  63. 1111111

    Returns: 11111117

  64. 1578808

    Returns: 157880851

  65. 1801625

    Returns: 180162511

  66. 2047890

    Returns: 204789001

  67. 2919165

    Returns: 29191651

  68. 6000000

    Returns: 600000001

  69. 7411995

    Returns: 74119951

  70. 7511812

    Returns: 75118129

  71. 10300131

    Returns: 1030013107

  72. 12834795

    Returns: 128347957

  73. 14124969

    Returns: 141249697

  74. 14311787

    Returns: 143117873

  75. 22222222

    Returns: 222222227

  76. 22249658

    Returns: 2224965803

  77. 23725878

    Returns: 237258787

  78. 32608533

    Returns: 3260853301

  79. 44780631

    Returns: 447806311

  80. 50000000

    Returns: 500000003

  81. 52768928

    Returns: 5276892821

  82. 72117357

    Returns: 721173577

  83. 109386516

    Returns: 1093865161

  84. 112052869

    Returns: 1120528699

  85. 114548465

    Returns: 1145484653

  86. 116055547

    Returns: 116055547

  87. 131400022

    Returns: 1314000223

  88. 136670088

    Returns: 13667008801

  89. 150794607

    Returns: 15079460701

  90. 163784738

    Returns: 16378473851

  91. 194539708

    Returns: 1945397081

  92. 283733899

    Returns: 2837338993

  93. 286544298

    Returns: 28654429841

  94. 369426272

    Returns: 36942627217

  95. 396477633

    Returns: 3964776331

  96. 396738453

    Returns: 39673845313

  97. 421294032

    Returns: 42129403229

  98. 444604326

    Returns: 44460432623

  99. 476656188

    Returns: 47665618813

  100. 492128229

    Returns: 4921282291

  101. 566292666

    Returns: 56629266649

  102. 611626153

    Returns: 6116261539

  103. 700751158

    Returns: 7007511587

  104. 784281966

    Returns: 78428196629

  105. 817750697

    Returns: 81775069709

  106. 842998321

    Returns: 84299832107

  107. 901340478

    Returns: 9013404787

  108. 906266052

    Returns: 90626605211

  109. 909911363

    Returns: 9099113633

  110. 920208788

    Returns: 9202087883

  111. 923504513

    Returns: 92350451321

  112. 926997684

    Returns: 92699768479

  113. 931474226

    Returns: 93147422611

  114. 945411576

    Returns: 9454115761

  115. 960879959

    Returns: 96087995903

  116. 965898657

    Returns: 96589865711

  117. 966396815

    Returns: 9663968159

  118. 968673580

    Returns: 96867358033

  119. 970903854

    Returns: 97090385411

  120. 972939857

    Returns: 97293985703

  121. 975645855

    Returns: 9756458557

  122. 976146682

    Returns: 97614668231

  123. 983489906

    Returns: 98348990603

  124. 985298711

    Returns: 98529871117

  125. 993286024

    Returns: 9932860241

  126. 999206390

    Returns: 99920639017

  127. 1000000000

    Returns: 100000000003

    This is the largest possible input.

  128. 32454

    Returns: 3245401

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: