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.
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.
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.
The space complexity of this program is O(1) as the number of memory spaces are constant for any given input.