Prime Number Program in C

A Prime Number is a positive integer greater than 1, which is divisible by one and itself; in other words, it has only two factors, one and itself. In this article, we will understand prime numbers in depth and learn how to write Prime Number Program in C.

Algorithms to Check Prime Numbers in C

There are two methods to check prime number in c. These are:

1. Simple Method
2. Using Sqrt(N)

Simple Method

Output:

Explanation:

• The function isPrime() takes an integer n as input and returns one if it is prime, and 0 otherwise.
• In the function, if the number is less than or equal to 1 (n <= 1), it's not prime, so we return 0.
• We then iterate through numbers from 2 to n-1 (for (int i = 2; i < n; i++)) and check if n is divisible by any of these numbers. If it is (if (n % i == 0)), then it's not prime, so we return 0.
• If none of the numbers from 2 to n-1 divide n, then it's prime, and we return 1.
• It is a simple c program to check whether a number is prime or not.

Using Sqrt(N)

Output:

Explanation:

• This method is similar to the simple method but with an optimization in the loop condition.
• Instead of checking divisibility up to n-1, we only need to check up to the square root of n. This is because if a number n has a divisor greater than its square root, then it must also have a divisor less than its square root.
• So, we iterate through numbers from 2 to sqrt(n) instead of n-1 (for (int i = 2; i <= sqrt(n); i++)).

C Programs to Check Prime Numbers in C

Now, let's learn how to write C program for prime number using functions,loops, pointers and recursion.

Using Functions

• The isPrime() function takes an integer n as input and returns 1 if n is prime; otherwise, it returns 0.
• It iterates from 2 to n-1 and checks if n is divisible by any number in this range. If it is, then it's not prime.
• If n passes all these conditions, it's considered prime.
• In the main() function, we call isPrime() with the number to check for primality and print the result.

Using Loops

• This program uses a loop to iterate over numbers from 2 to num-1.
• Inside the loop, it checks if num is divisible by any number in this range. If it is, then num is not prime.
• If num is divisible by any number, we set isPrime flag to 0, indicating that num is not prime.
• If num passes the loop without being divisible by any number, it's considered prime.
• Finally, we print the result based on the value of the isPrime flag.

Using Pointers

• This program is similar to the "Using Functions" program, but it takes a pointer to an integer as input instead of an integer directly.
• Inside the isPrime() function, we dereference the pointer to access the actual integer value.
• The rest of the logic remains the same as the "Using Functions" program.
• In the main() function, we declare an integer num, obtain a pointer to it, and pass this pointer to the isPrime() function.

Using Recursion

• This program uses recursion to check for primality.
• The isPrime() function takes two arguments: the number n to check and the current divisor i.
• It first handles base cases where n is less than or equal to 2 or when i * i > n.
• Inside the function, it checks if n is divisible by i. If it is, n is not prime.
• If n passes all conditions, it's considered prime.
• In the main() function, we call isPrime() with the number to check for primality and the initial divisor value of 2 and print the result.

Using all the above methods, we can check whether a number is a Prime number or not in C language.