## Q. Write an algorithm and program to Check Whether a Number is Prime or not?

The article will help you write a algorithm and program to Check Whether a Number is Prime or not.

Prime Number:- A number that is divisible by only and only 1 and itself is known as a Prime Number. For example: - 11 is only divisible by 1, so 11 is prime, while 10 is divisible by 1, 2, and 5 so 10 is not a prime number.

Here you will find the algorithm and program to check whether a number is prime or not with explanation.

## Prime Number Algorithm

```START
Step 1 → Take integer variable A
Step 2 → Divide the variable A with (A/2 to 2)
Step 3 → If A is divisible by any value (A/2 to 2) then it is not prime
Step 4 → Else it is prime number
STOP
```

# Prime Number Program

• C
• C++
• Java
• Python
• PHP
• ```#include <stdio.h>
int main() {
int n, i, flag = 0;
printf("Enter a positive integer: ");
scanf("%d", &n);
for (i = 2; i <= n / 2; ++i) {
// condition for non-prime
if (n % i == 0) {
flag = 1;
break;
}
}
if (n == 1) {
printf("1 is neither prime nor composite.");
}
else {
if (flag == 0)
printf("This is a prime number.");
else
printf("This is not a prime number.");
}
return 0;
}
```
```#include <iostream>
using namespace std;
int main()
{
int n, i;
bool isPrime = true;
cout << "Enter a positive integer: ";
cin >> n;
for(i = 2; i <= n / 2; ++i)
{
if(n % i == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
cout << "This is a prime number";
else
cout << "This is not a prime number";
return 0;
}
```
```import java.util.Scanner;
class PrimeCheck
{
public static void main(String args[])
{
int temp;
boolean isPrime=true;
Scanner scan= new Scanner(System.in);
System.out.println("Enter a positive number:");
//capture the input in an integer
int num=scan.nextInt();
scan.close();
for(int i=2;i<=num/2;i++)
{
temp=num%i;
if(temp==0)
{
isPrime=false;
break;
}
}
//If isPrime is true then the number is prime else not
if(isPrime)
System.out.println(num + " is a Prime Number");
else
System.out.println(num + " is not a Prime Number");
}
}
```
```# To take input from the user
num = int(input("Enter a positive integer: "))
# prime numbers are greater than 1
if num > 1:
# check for factors
for i in range(2,num):
if (num % i) == 0:
break
else:
print(num,"is a prime number")
# if input number is less than
# or equal to 1, it is not prime
else:
print(num,"is not a prime number")
```
```function primeCheck(\$number){
if (\$number == 1)
return 0;
for (\$i = 2; \$i <= \$number/2; \$i++){
if (\$number % \$i == 0)
return 0;
}
return 1;
}
// Driver Code
\$number = 31;
\$flag = primeCheck(\$number);
if (\$flag == 1)
echo "31 is a prime number.";
else
echo "31 is Not a prime number."
```
```#include <stdio.h>
int main() {
int n, i, flag = 0;
printf("Enter a positive integer: ");
scanf("%d", &n);
for (i = 2; i <= n / 2; ++i) {
// condition for non-prime
if (n % i == 0) {
flag = 1;
break;
}
}
if (n == 1) {
printf("1 is neither prime nor composite.");
}
else {
if (flag == 0)
printf("This is a prime number.");
else
printf("This is not a prime number.");
}
return 0;
}
```

#### Output

```Enter a positive integer : 17
This is a prime number.
Enter a positive integer : 25
This is not a prime number.
```

## Recommended Programs

Program to find sum of array elements
Program to find smallest element in an array