C# program to check if a number is a prime or not has been shown here. A positive number $n$ is called a prime, if it does not have any divisor except $1$ and $n$. For example if $n = 13$, it is prime but if $n = 10$, it is not prime as $10$ is divisible by $2$ and $5$ apart from $1$ and $10$. The algorithm, pseudocode and time complexity of the program have been shown below.

## 1. Algorithm to check if a number is a prime or not

1. Take a positive number n as input.

2. Check for each i $\in$ [2, $\sqrt{n}$], if n is divisible by i

3. If step 2 is true for atleast one i, then n is not a prime.

4. If step 2 is false for each i, then n is a prime.

## 2. Pseudocode to check if a number is a prime or not

Input : A postive number $n$

Output : $n$ is a prime or not a prime

1. Procedure checkPrime($n$):

2. $flag \leftarrow 0$

3. Repeat for $i \in [2, \sqrt{n}]$:

4. If $n \mod i$ = 0:

5. $flag \leftarrow 1$

6. break

7. If $n = 1$

8. Return "not a prime"

9. Else:

10. If $flag = 1$:

11. Return "not a prime"

12. Else:

13. Return "a prime"

14. End Procedure

## 3. Time complexity to check if a number is a prime or not

Time Complexity: O($\sqrt{n}$)

Where n is the input number.

## 4. C# Program & output to check if a number is a prime or not using iteration

Code has been copied
/*********************************
alphabetacoder.com
C# program to check if a number
is a prime or not using iteration
***********************************/

using System;

namespace CheckPrime {
class Program {
static void Main(string[] args) {
// declare variables
int n, i, flag = 0;

// take input of the number
Console.Write("Enter the number = ");

// check if n is a prime or not
// If n has divisor between 2 and
// square root of n, then
// n is not prime else n is prime
for (i = 2; i <= Math.Sqrt(n); i++) {
if (n % i == 0) {
flag = 1; // mark as not prime
break; // exit from loop
}
}

// dispay the result
if (n == 0 || n == 1)
Console.Write(n + " is neither a prime nor a composite!");
else {
if (flag == 0)
Console.Write(n + " is a prime!");
else
Console.Write(n + " is not a prime!");
}
}
}
}


Output

Enter the number = 101

101 is a prime!

## 5. C# Program & output to check if a number is a prime or not using recursion

Code has been copied
/*********************************
alphabetacoder.com
C# program to check if a number
is a prime or not using recursion
***********************************/

using System;

namespace CheckPrime {
class Program {
// recursive function to check
// if a number is prime or not
// check divisor upto sqrt(num)
static int check_prime(int num, int i) {
// return 1, as num is prime
if (i > Math.Sqrt(num))
return 1;
// return 0, as num is not prime
if (num % i == 0)
return 0;
// call function
return check_prime(num, i + 1);
}

static void Main(string[] args) {
// declare variables
int n;

// take input of the number
Console.Write("Enter the number = ");

//check if n is a prime or not
// by calling the function
// if the function returns 1,
// it is considered prime else
// it is considered not prime
if (n == 0 || n == 1)
Console.Write(n + " is neither a prime nor a composite!");
else {
if (check_prime(n, 2) == 1)
Console.Write(n + " is a prime!");
else
Console.Write(n + " is not a prime!");
}
}
}
}


Output

Enter the number = 37

37 is a prime!