## Prime Number

Back to Programming

### Description

A number is called prime number if the number is only divisible by 1 and itself. The prime numbers has exactly two factors- 1 and the number itself.

For example – 5. 5 is only divisible by 1 and 5. The number of factors of 5 is 2. So, 5 is a prime number.

If the number is 4, it is divisible by 1, 2 and 4. So, instead of 1 and 4, it has another factor 2. The number of factors of 4 is 3. So, it is not a prime number.

So, the main logic of the program is to take the number as input and the number of factors are counted. If the number of factor is 2 then it is a prime number otherwise it is not a prime number.

### Algorithm

INPUT: A number.

OUTPUT: Whether it is a prime number or not.

PROCESS:

Step 1: [Taking the input]

Read n [the number which is to be checked]

Step 2: [Checking for the prime number]

Set c<-0

For i=1 to n repeat

If n mod i=0 then

Set c<-c+1

[End of ‘if’]

[End of ‘for’ loop]

If c=2 then

Print "Prime Number"

Else

Print "Not a prime number"

[End of ‘if’]

Step 3: Stop.

## TIME COMPLEXITY:

Here for this program, the time complexity to check whether a number is a prime number or not is O(n) where n is the given input. For the simplicity of the program the loop has been written from 1 to n to check for a prime number.

But for more optimization we can check from 2 to  $\sqrt{n}$  because a number ‘n’ can have maximum $\sqrt{n}$  number of factors. So, we can say most optimized complexity is O($\sqrt{n}$).

## SPACE COMPLEXITY:

The space complexity of this program is O(1) as it requires a constant number of memory spaces to execute the program.