infinite loop when user enter a large number

Question

I'm writing a function called largestTwinPrime where it takes in 2 numbers and finds the largest twin prime number between the two. My program works however when the user enters a large enough number the program becomes an infinite loop. For example:

largestTwinPrime(0, 15485661) would give me this error "Program exceeded its time limit and was stopped (possible infinite loop)".
largestTwinPrime(1, 18) would output 17.

This is the code I have and thanks for the help!

(isPrime)

int isPrime(int num){
    if(num <= 1) return 0;
    for (int i = 2; i * i <= num; i++){
        if (num % i == 0) return 0;
    }
    return 1;
}

(isTwinPrime)

bool isTwinPrime(int n){
    if(n <= 1) return 0;
    if(isPrime(n+2)==true && isPrime(n)==true){
        return 1;
    } else if(isPrime(n-2)==true && isPrime(n)==true){
        return 1;
    } else{
        return 0;
    }
}

(largestTwinPrime)

int largestTwinPrime(int a, int b){
    int answer=0;
    while(a <= b){
        for(int i = a; i <= b; i++){
            if(isTwinPrime(i)== true){
                answer = i;
            }
        }
        a++;
    }
    if(answer==0) return -1;
    else return answer;
}

Might not be infinite. It looks like you have a brute force algorithm. These are almost always too slow. You need to figure out at least one of the *tricks* the judging site expects you to use to solve the problem quickly. For example, if you are hunting primes and not using some sort of sieving algorithm and memoization, you're not going to hit the performance requirement. — user4581301, Mar 04 '19 at 06:54
You need to show your `isTwinPrime` function. It is probably extremely inefficient — Jabberwocky, Mar 04 '19 at 07:00
Possible duplicate of [Finding biggest prime number in user-inputted number - C](https://stackoverflow.com/questions/54688889/finding-biggest-prime-number-in-user-inputted-number-c) — Jabberwocky, Mar 04 '19 at 07:02
See [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and do a quick search here for an implementation. — David C. Rankin, Mar 04 '19 at 07:28
Perhaps [Sieve of Eratosthenes implementation](https://stackoverflow.com/questions/15980599/sieve-of-eratosthenes-implementation) — David C. Rankin, Mar 04 '19 at 07:38

score 0 · Accepted Answer · edited Jun 20 '20 at 09:12

Your code has a very poor complexity. Your code is invoking isTwinPrime O(n²) times which totals over O(n^2.5). This makes it look like an infinite loop:

while(a <= b){ // O(N) iterations
    for(int i = a; i <= b; i++){
        // times O(N) = O(N**2)
        if(isTwinPrime(i)== true){ // The call is over O(sqrt(N))
            answer = i;
        }
    }
    a++;
}

The correct code is:

int largestTwinPrime(int a, int b){
    int answer=0;
    if (b < 5) return -1;
    // A twin prime is odd, so go over odd values.
    if (b %2 == 0) b--; 
    for(int i = b; i >= a; i-=2){
            if(isTwinPrime(i))
                return i;
    }
    return -1;
}

Complexity is lower by a factor of O(N).

EDIT

Also, your isPrime is inefficient. Better to fill a vector of primes below sqrt(N) (using the Sieve of Eratosthenes), and use that to speed up the validation of primes.

infinite loop when user enter a large number

1 Answers1

EDIT