## Prime Number in C

A prime number in C is a Positive Number that can be divided exactly only by itself.

## What is a prime number?

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. In other words, a prime number is a number that can only be divided evenly by 1 and itself.

For example, the first six prime numbers are 2, 3, 5, 7, 11, and 13. These numbers can only be divided evenly by 1 and themselves. The number 4, for example, is not a prime number because it can be divided evenly by 2 and itself.

Prime numbers play an important role in number theory and have many applications in computer science and cryptography.

## Approach to check prime number in C language

Here is one approach to check whether a given number is prime in C:

- First, check for the base cases. If the number is less than or equal to 1, it is not prime and the function can return 0. If the number is 2 or 3, it is prime and the function can return 1.
- Next, check for divisibility by 2 and 3. If the number is divisible by 2 or 3, it is not prime and the function can return 0.
- To check for divisibility by other integers, use a for loop to iterate through all integers in the range [5, sqrt(n)]. For each integer, check if the number is divisible by it or by (it+2). If it is divisible by any of these integers, it is not prime and the function can return 0.
- If the number has passed all the checks above, it is considered prime and the function can return 1.

## Pseudo code to check prime number in C language

Here is some sample pseudocode for checking whether a given number is prime in C:

```
int is_prime(int n) {
if (n <= 1) {
return 0;
}
if (n <= 3) {
return 1;
}
if (n % 2 == 0 || n % 3 == 0) {
return 0;
}
for (int i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return 0;
}
}
return 1;
}
```

This code uses a simple algorithm to check whether the input number is prime. It first checks for the base cases (n <= 1 and n <= 3), then checks if the number is divisible by 2 or 3. If the number passes those checks, it uses a for loop to check for divisibility by all integers in the range [5, sqrt(n)]. If the number is not divisible by any of those integers, it is considered prime and the function returns 1. Otherwise, it returns 0.

## C program to check prime numbers.

Here is a sample C program that uses the approach I described earlier to check whether a given number is prime

```
#include <stdio.h>
#include <math.h>
int is_prime(int n) {
if (n <= 1) {
return 0;
}
if (n <= 3) {
return 1;
}
if (n % 2 == 0 || n % 3 == 0) {
return 0;
}
for (int i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return 0;
}
}
return 1;
}
int main() {
int num;
printf("Enter a positive integer: ");
scanf("%d", &num);
if (is_prime(num)) {
printf("%d is a prime number\n", num);
} else {
printf("%d is not a prime number\n", num);
}
return 0;
}
```

This program uses the `is_prime`

function to check whether a given number is prime. The user is prompted to enter a positive integer, and the function is called with this number as an argument. The function returns 1 if the number is prime and 0 if it is not. The program then prints the appropriate message to the console.

Other Programs :