Finding a prime number at least a 100 digits long that contains 273042282802155991

Question

I am new to Java and one of my class assignments is to find a prime number at least 100 digits long that contains the numbers 273042282802155991.

I have this so far but when I compile it and run it it seems to be in a continuous loop.

I'm not sure if I've done something wrong.

public static void main(String[] args) {
    BigInteger y = BigInteger.valueOf(304877713615599127L);
    System.out.println(RandomPrime(y));
}

public static BigInteger RandomPrime(BigInteger x)
{
    BigInteger i;

    for (i = BigInteger.valueOf(2); i.compareTo(x)<0; i.add(i)) {
        if ((x.remainder(i).equals(BigInteger.ZERO))) {
            x.divide(i).equals(x);
            i.subtract(i);
        }
    }
    return i;
}

Answer 1

Since this is homework ...

1. There is a method on BigInteger that tests for primality. This is much much faster than attempting to factorize a number. (If you take an approach that involves attempting to factorize 100 digit numbers you will fail. Factorization is believed to be an NP-complete problem. Certainly, there is no known polynomial time solution.)

2. The question is asking for a prime number that contains a given sequence of digits when it is represented as a sequence of decimal digits.

3. The approach of generating "random" primes and then testing if they contain those digits is infeasible. (Some simple high-school maths tells you that the probability that a randomly generated 100 digit number contains a given 18 digit sequence is ... 82 / 10¹⁸. And you haven't tested for primality yet ...

4. But there's another way to do it ... think about it!

Only start writing code once you've figured out in your head how your algorithm will work, and done the mental estimates to confirm that it will give an answer in a reasonable length of time.

---

_{When I say infeasible, I mean infeasible for you. Given a large enough number of computers, enough time and some high-powered mathematics, it may be possible to do some of these things. Thus, technically they may be computationally feasible. But they are not feasible as a homework exercise. I'm sure that the point of this exercise is to get you to think about how to do this the smart way ...}