FOR FREE CONTENT

Prime Numbers between 1 and 100

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,  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.

Algorithm

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.

Code

TIME COMPLEXITY:

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 j because a number ‘j’ can have maximum j number of factors. So, we can say most optimized complexity is O(j).

SPACE COMPLEXITY:

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.