c++ function to check if a number is a prime

Question

bool prime (long long int n) {
    bool prime = 1;
    if (n == 1) {
        return 0;
    }
    else {
        for (long long int i = 2; i <= n/2 ; i++) {
            if (n % i == 0) {
                prime = 0;
                break ;
            }
            
        }
        return prime;
    }
}

This is my function to check if n is a prime or not. It works until I try a number with 12 digits, like n = 999999999989.

This is for a problem on codeforces; when I submit this function the website prints "Time limit exceeded".

Answer 1

Your code's time complexity is O(n/2) -> O(n). It would take around 10000 second to check the primality of n if n is 10^12 (given 1 second can only do around 10^8 operation).

for (long long int i = 2; i <= n/2 ; i++) {
    if (n % i == 0) {
        prime = 0;
        break ;
}

The trick here is that you don't need to check i from 2 to n/2. Instead, you can reduce it to just from 2 to sqrt(n). This work because since sqrt(n) * sqrt(n) is n, there shouldn't be any x and y so that x > sqrt(n); y > sqrt(n); x*y = n. Thus, if a divisor for n exist, it should be <= sqrt(n).

So you should change your loop to this

for (long long int i = 2; i*i <= n ; i++) {
    if (n % i == 0) {
        prime = 0;
        break ;
    }
}

The time complexity for this code is O(sqrt(n)) which should be enough for n = 10^12.

P.S : sqrt(n) means square root of n