Prime Number Program using C

2. Check for Prime Number using sqrt(n)

An optimized method to check if a number n is prime is to only test divisibility up to the square root of n. This is because if n has a divisor greater than its square root, the corresponding co-divisor will be less than the square root. Thus, it’s sufficient to check divisibility only up to √n.

For example : 

• C

C

#include <stdio.h>
#include <math.h> // Include to use sqrt function

int isPrime(int n) {
    if (n <= 1) return 0; // 0 and 1 are not prime numbers
    if (n <= 3) return 1; // 2 and 3 are prime numbers

    if (n % 2 == 0 || n % 3 == 0) return 0; // Quick check for divisibility by 2 or 3

    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return 0; // n is divisible by some number other than 1 and itself
        }
    }
    return 1; // n is a prime number
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);

    if (isPrime(num))
        printf("%d is a prime number.\n", num);
    else
        printf("%d is not a prime number.\n", num);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

In this program, the isPrime function first eliminates numbers less than 2 and any even numbers greater than 2. It then checks for divisibility using numbers from 5 up to the square root of n, incrementing by 6 each time to skip even numbers and multiple of 3 (since these are already checked). If no divisors are found within this range, n is determined to be prime. This approach significantly reduces the number of checks needed, especially for large numbers.

FAQs

What is a prime number?

A number n is called a prime number if it is only divisible by 1 and the number itself. Prime numbers are more than the number 1 and have precisely two factors: 1 and the number itself.
 

What is the logic of finding prime numbers using the C language?

To check whether a number n is prime or not, we will have to divide n by each number from 2 to n-1. If n is divisible by any number, it is not a prime number, and if no number can divide n, then n is prime. C language provides various looping statements through which our task of checking whether a number is prime or not can be carried out smoothly. 
 

Why is 2 a prime number?

2 is the only even prime number that exists because it has only two factors 1 and itself.

Conclusion

In this blog, we discussed about two easy-to-learn approaches to check the prime number. First, we discussed the “Simple method” which is very to understand as we just have to use the loop in C, and then we use the “Sqrt method” of C, this process significantly reduces the checks needed, which is very useful to save the CPU time for the large numbers.