**Before see the program follow** the ** prime number checking program**.

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

For example, if **the number is 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.

The program is written here to **find the prime numbers between 1 and 100**. For each number it is checked for prime, if it is prime then it will be printed.

```
OUTPUT: Prime numbers between 1 and 100.
PROCESS:
Step 1: [printing the prime numbers between 1 and 100]
For j=1 to 100 repeat
Set c<-0
[counting the number of factors]
For i=1 to j repeat
If j mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
If c=2 then
Print j
[End of ‘if’]
Step 2: Stop.
```

for(j=1;j<=100;j++)----------------------------------O(100)

{ c=0;

//counting the number of factors

for(i=1;i<=j;i++)---------------------------O(j)

{

if(j%i==0)------------------------O(1)

c++;

}

if(c==2)-------------------------------------O(1)

printf("%d ",j);

}

The **time complexity of finding prime numbers** here is **O(n*j**) where **n is the number of elements** to **be checked for prime and ‘j’ is each number to be checked**. Here, the value of **n is 100**. For the simplicity of the program here the loop to check prime is executed from 1 to j.

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

The **space complexity of this program** is **O(1)** as it requires a constant number of memory spaces to find the prime numbers between 1 and 100.