C - Determine If a Number Is Prime

C - determine if a number is prime

OK, so forget about C. Suppose I give you a number and ask you to determine if it's prime. How do you do it? Write down the steps clearly, then worry about translating them into code.

Once you have the algorithm determined, it will be much easier for you to figure out how to write a program, and for others to help you with it.

edit: Here's the C# code you posted:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

This is very nearly valid C as is; there's no bool type in C, and no true or false, so you need to modify it a little bit (edit: Kristopher Johnson correctly points out that C99 added the stdbool.h header). Since some people don't have access to a C99 environment (but you should use one!), let's make that very minor change:

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

This is a perfectly valid C program that does what you want. We can improve it a little bit without too much effort. First, note that i is always less than number, so the check that i != number always succeeds; we can get rid of it.

Also, you don't actually need to try divisors all the way up to number - 1; you can stop checking when you reach sqrt(number). Since sqrt is a floating-point operation and that brings a whole pile of subtleties, we won't actually compute sqrt(number). Instead, we can just check that i*i <= number:

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

One last thing, though; there was a small bug in your original algorithm! If number is negative, or zero, or one, this function will claim that the number is prime. You likely want to handle that properly, and you may want to make number be unsigned, since you're more likely to care about positive values only:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

This definitely isn't the fastest way to check if a number is prime, but it works, and it's pretty straightforward. We barely had to modify your code at all!

Algorithm of checking if the number is prime

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1

Implementation of the above:

#include <iostream>

bool isPrime(int n) {
    // Corner cases
    if(n <= 1) return false;
    if(n <= 3) return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if(n % 2 == 0 || n % 3 == 0) return false;

    for(int i = 5; i * i <= n; i = i + 6)
        if(n % i == 0 || n % (i + 2) == 0) return false;

    return true;
}

// Driver Program to test above function
int main() {
    std::cout << std::boolalpha
        << isPrime(11) << '\n'
        << isPrime(15) << '\n';
}

C - how to test easily if it is prime-number?

The easiest way is writing a loop, like:

int is_prime(int num)
{
     if (num <= 1) return 0;
     if (num % 2 == 0 && num > 2) return 0;
     for(int i = 3; i < num / 2; i+= 2)
     {
         if (num % i == 0)
             return 0;
     }
     return 1;
}

You can then optimize it, iterating to floor(sqrt(num)).

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

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

Finding whether a number is prime or not c++

The loop

for (int i=5; i*i<=n; i=i+6)
  if (n%i == 0 || n%(i+2) == 0)
    return false;

could have been written as:

for (int i=5; i*i<=n; i=i+2)
  if (n%i == 0 )
    return false;

for easier understanding. You check whether the number is divisible by:

5 7 9 11 13, etc.

If you rearrange those odd numbers as:

5 7 9
11 13 15
17 19 21
23 25 27

etc.,

you'll notice that the all the numbers in the last column are multiples of 3. If any number is divisible by those, they are divisible by 3 also. Since the function already checks whether the number is divisible by 3 at the beginning, it's not necessary to check that. Hence, we need to check whether the number is divisible only by:

5 7 
11 13
17 19
23 25

etc.

The patter for those number is:

i i+2

with the increment between the rows being 6. You can translate that to:

1. Start with i = 5
2. Check whether the number is divisible by i or i+2. If so, return false.
3. Increment i by 6 and repeat.

That's what the for loop does.

Why is the conditional of the for statement i*i <= n?

That's because a number cannot be divisible by any number greater than its square root. If you reach the point where i*i > n, you are assured that n is not divisible by i. Continuing with the loop for any i greater than that will not change the value of the conditional. The number is a prime number when we reach that point.

To find a number is prime, Why checking till n/2 is better. What is the reason for avoiding numbres in second half of n

Because, the smallest multiple that will not make it a prime is 2. If you have checked all the numbers from 0 to n/2, what multiple is left that could possibly work? If multiple by 2 is bigger than n, then a multiple of 3 or 4 etc will also be bigger than n.

So the largest factor for any number N must be <= N/2

So yes take N/2, and check all integers smaller or equal to N/2. So for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

The square root is explained here:
Why do we check up to the square root of a prime number to determine if it is prime?

And this question has been asked before.

---

Related Topics