FOR FREE CONTENT
Prime Factors of range of Numbers
Back to ProgrammingDescription
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.
