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".

You only have to check up to the square root of the number. q.v. https://stackoverflow.com/a/1101217/4641116 — Eljay, Jan 29 '22 at 14:29
@AlanBirtles A sieve is not helpful if your task is to check primality of a single number. — interjay, Jan 29 '22 at 14:49
@AlanBirtles Rather this direction: https://en.m.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test — πάντα ῥεῖ, Jan 29 '22 at 15:05

score 2 · Accepted Answer · answered Jan 29 '22 at 14:46

2

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

answered Jan 29 '22 at 14:46

TypeYippie

36
1

2

you don't need to check the even numbers (apart from 2) – Alan Birtles Jan 29 '22 at 14:52
@AlanBirtles Actually you only need to check primes. (That can be arranged with a bit of recursion. ) Some folk question the purity of skipping evens - as you're sort of "hard coding" that. – Bathsheba Jan 29 '22 at 14:56
Note that `i <= n / i` is a better way of writing the stopping conditional as it avoids a potential overflow of an integral type. Nice answer though. Have an upvote. – Bathsheba Jan 29 '22 at 14:56
@AlanBirtles You're right. But I don't think it really impact much on the time complexity – TypeYippie Jan 29 '22 at 15:21
@Bathsheba Yeah You're also right, thanks for the suggestion. – TypeYippie Jan 29 '22 at 15:22
It'll make it twice as fast... – Alan Birtles Jan 29 '22 at 15:22
@AlanBirtles - perhaps. Or you could get the compiler to calculate them - so O(1) at runtime. – Bathsheba Jan 29 '22 at 19:12
Speaking of code optimizations: do **not** use the post-increment operator (`i++`) in a for loop. The post-increment operator [creates a temporary copy](https://stackoverflow.com/questions/30941980/why-post-increment-needs-to-make-a-copy-while-pre-increment-does-not) that's not needed here. So, just stick to the pre-increment operator `++i`. – Karoly Nyisztor Apr 12 '23 at 12:15

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

1 Answers1