Q.10: How to find if a positive integer is a prime number or not?

 Ans.: The user will input a positive integer and the method should output “Prime” or “Not Prime” based on whether the input integer is a prime number or not.

The logic is to find a positive integer less than or equal to the square root of input integer. If there is a divisor of number that is less than the square root of number, then there will be a divisor of number that is greater than square root of number. Hence, we have to traverse till the square root of number.

The time complexity of this function is O(√N) because we traverse from 1 to √N.

• input: 20, output: Not Prime
• input: 17, output: Prime

static void Main(string[] args)

{

if (FindPrime(47))

{

Console.WriteLine("Prime");

}

else

{

Console.WriteLine("Not Prime");

}

Console.ReadLine();

}

internal static bool FindPrime(int number)

{

if (number == 1) return false;

if (number == 2) return true;

if (number % 2 == 0) return false;

var squareRoot = (int)Math.Floor(Math.Sqrt(number));

for (int i = 3; i <= squareRoot; i += 2)

{

if (number % i == 0) return false;

}

return true;

}