PrimeWithSubstring | Topcoder Archive

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

```
47
```
```
Returns: 47
```
The number itself is a prime, so Jaro is in luck.
```
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".
```
0
```
```
Returns: 4021
```
Now 4021 is a perfectly acceptable answer.
```
123456789
```
```
Returns: 312345678971
```
Watch out for integer overflow, the answers are sometimes too big for a 32-bit data type.
```
111
```
```
Returns: 2111
```
```
1000000000
```
```
Returns: 100000000003
```
This is the largest possible input.

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.