CODEWITHSUNDEEP
javaalgorithmdynamic-programming
Vksgh
Vksgh

Reputation: 91

prime factor of a number

Here is the Question 

f(x)=sum of power of prime factor of x
now if f(x) is given then find the least value of x which also setisfy the condition
(No of divisor of x)-1=f(x).
Eg: f(x)=2 given and i need to find x 
Step 1:check for x=2 then f(x)=1
Step 2:check for x=3 then f(x)=1
Step 3: check for x=4 then f(x)=2 (i.e-x=2^2,and we know that f(x) is some of power of prime factor so f(x) here is 2)
And divisor of 4 is 1,2 & 4 so ,no of divisor -1=f(x)

so the Answer is x=4.

Now the approach i followed
Step 1-start for i=2 till we get the answer
step 2-find the prime factor for i and calculate the sum of power
Step 3-check if calculated sum is equal to the f(x) or not if not then increment i and repeat from step -1.

Now my question is

  1. I am starting from i=2 and checking for f(x) by increment i by 1 each time . is there any efficient way to do that?
    1. Also i am continuing the loop till i get the answer. can it be done with some other end condition because it might go in infinite loop? Please help

Upvotes: 4

Views: 80

Answers (1)

Masked Man
Masked Man

Reputation: 2568

Every number can be represented in the form of:

x = a1p1.a1p1...anpn

Where:

ai 1 <= i <= n are prime factors.

So for the x to be minimum possible all factors should be 2and so the x would be 2 ^ f(x).

Number of divisors of x is: (p1 + 1)(p2 + 1)...(pn + 1) so your added condition also will be satisfied!

Upvotes: 4

Related Questions