Prime factors of a number

Back to Programming

Description

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.

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.