FOR FREE CONTENT
Prime factors of a number
Back to ProgrammingDescription
Here the program is written to find the prime factors of a number. A number is taken as input. After that we have to find the factors of the number 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 input be 20. 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.
Algorithm
INPUT: A number.
OUTPUT: The prime factors of the number.
PROCESS:
Step 1: [Taking the input]
Read n [The number of which the prime factors are to be printed]
Step 2: [Find the prime factors]
For i=1 to n repeat
[finding the factors of n]
If n 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]
Step 3: Stop.
Code
TIME COMPLEXITY:
for(i=1;i<=n;i++)---------------------------------------O(n)
{
//finding the factors of n
if(n%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);
}
}
The time complexity of this program is O(n*i) where ‘n’ is the given number and ‘i’ is each factor of the given number.
SPACE COMPLEXITY:
The space complexity of this program is O(1) as the number of memory spaces are constant for any given input.
