Gift distance

... by Bittle in Programming Help August 17, 2018


You are on your way to find the gifts. All the gifts lie in your path in a straight line at prime numbers and your house is at 0.

Given your current position find the closest gift to your position, and calculate the distance between your current position and gift and tell the distance.


The problem is asking what the nearest prime to the current location is. Every prime is surrounded by other numbers (869, 870, ...) which can be prime; for example, 870 has the prime 877 close to it, but also 863, they are both 7 numbers away, resulting in the output of 7, but if that wasn't the case, then the closest prime distance would be the answer.

We first need a way to know when a number is prime, which requires simple math:

private static boolean check_prime(long n) {
    for(long i = 2; i<Math.sqrt(n);i++) {
            return false;
    return true;

or you can use the built in function of big integer to check for primes:

private static boolean check_prime(long n)
    // Converting long to BigInteger
    BigInteger b = new BigInteger(String.valueOf(n));

    return b.isProbablePrime(1);

Once you have that, you have to loop to both sides of the number and continuously check if the number that you looped to is prime, like so:

while (true) {
    long number, i;

    // get input from keyboard
    Scanner scanner = new Scanner(;
    number = scanner.nextLong();

    if (check_prime(number))
        // if already prime, just print 0
    else {
        // loop to both sides of the number
        for (i = 1; i < number - 2; i++) {
            // this print is for debugging purposes
            System.out.println((number - i) + ", " + (number + i));
            if (check_prime(number - i)) {
                // found answer as prime before input
                System.out.printf("%d\n", (number - (number - i)));
            } else if (check_prime(number + i)) {
                // found answer as prime after input
                System.out.printf("%d\n", ((number + i) - number));

Hope this helped!

Comments (0)

Search Here