FOR FREE CONTENT

Prime Factors of range of Numbers

Back to Programming

Description

Here the program is written to find the prime factors of numbers between a given ranges. The ranges are taken as inputs. After that we have to find the factors of the numbers and then the factors are to be checked as prime or not.

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.

For example:

Let the range be 20 to 30. The factors of 20 are 1, 2, 4, 5, 10 and 20. According to the logic of the prime number, 2 and 5 are primes among the factors of 20. Therefore, the prime factors of 20 are: 2 and 5.

Here, the factors includes 1 and the number itself.

Similarly, the prime factors will be calculated for the next numbers i.e. from 21 to 30 and the prime factors will be printed.

Algorithm

INPUT: Ranges of number.

OUTPUT: The prime factors of the numbers.

PROCESS:

Step 1: [Taking the input]

               Read m, n [The range of numbers]

Step 2: [Find the prime factors]

               For k=m to n repeat

                              For i=1 to k repeat

                                             [finding the factors of k]

                                             If k mod i=0 then

                                                            [Checking if the factor is prime or not]

                                                            Set c<-0

                                                            For j=1 to i repeat

                                                                           If i mod j=0 then

                                                                                          Set c<-c+1

                                                                           [End of ‘if’]

                                                            [End of ‘for’ loop]

                                                            [Checking for prime number]

                                                            If c=2 then

                                                                           Print i

                                                            [End of ‘if’]

                                             [End of ‘if’]

                              [End of ‘for’ loop]

                              Move to the next line

               [End of ‘for’ loop]

Step 3: Stop.

Code

TIME COMPLEXITY:

for(k=m;k<=n;k++)-------------------------------------O(p)

               {

                              printf("The prime factors of %d are: ",k);

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

                              {

                                             //finding the factors of n

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

                                             {

                                                            //checking if the factor is prime or not

                                                            c=0;

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

                                                            {

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

                                                                                          c++;

                                                            }

                                                            //checking for prime number

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

                                                                           printf("%d ",i);

                                             }

                              }

                              printf("\n");         

               }

The time complexity of this program is O(p*k*i) where ‘p’ is the numbers between the ranges, ‘k’ is the number to be checked as prime, ‘i’ is each factor of the number ‘k’.

SPACE COMPLEXITY:

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