How to find two prime numbers(can be same),such that its product is equal to given number.
for eg.
21= 7*3
4= 2*2I assume you are asking the following:
Given a number X, find two primes p1 and p2 ( p1 can be equal to p2) such that p1*p2 = X.
If you notice, products of prime numbers that give a certain number is called it’s prime factorization.
So basically you need to find prime factorization of X, the sum of powers of primes in prime factorization should be equal to 2, for an answer to exist.
e.g. 25 : 5^2, p1 = 5, p2 = 5;
10 : 2^1,5^1, p1 = 2, p2 = 5;
Pseduocode: Time complexity = O(sqrt(N)), space complexity = O(logN)
N = input()
factors = []
for i in range(2,sqrt(N)+1):
while( N%i == 0) :
N/=i
factors.append(i)
if N > 2:
factors.append(N)
if factors.size() != 2:
print("No Answer")
else:
print(factors[0],factors[1])One O(n) approach could be to just apply Sieve and then iterate through every prime number and check for the quiescent if it is also a prime. If it is then you got your answer. Else, no such factorization exists.
1 Like
@ayushagg31 I am aware of an algo that takes sqrt(N), for finding prime factors of a single number instead of a range. Can you please tell me whats the O(logN) approach
@utkalsinha Yes you are correct but i am not talking about the query problems. I was just talking about finding the prime factors of a single number, why would i use sieve then and with that i could easily find all the prime factors of a given number. I guess you were talking about queries that’s true. Hope I made it clear:) and @ayushagg there was nothing to feel sorry for it. Cheers 
1 Like
its cheating to ask questions from live contests , nowadays people really donot post questions , they just ask the way to do . this one was from india hack(hackerearth). he asked it on sundae . the contest ended on sunday night. this is real cheating
3 Likes
@code_man sqrt(n) is not the complexity for sieve. It is just for a problem like this. Given a number … find all the prime factors. So you can run a loop till sqrt(n). For algorithm visit Efficient program to print all prime factors of a given number.
Now precomputation is calculating all the prime numbers in a range say 1 to N
and not a single number. This is helpful when there are lots of queries.
Initially all the numbers is range marked true ,(assume all are prime) then All the composite number are marked false with the help of the nested loops.
You can read more about it here Sieve of Eratosthenes - GeeksforGeeks.
It’s a little hard to explain it completely but after reading if you get any doubt please revert back
- lets take number 21…
- 21%3=0 and 3 is a prime number…
21%7=0 and 7 is a prime number…
and 7*3=21… - . while other numbers between 0 and
21
does not follow the condition.
for ex 11 is a prime number but
21%11!=0…
so only 7 and 3 are the prime numbers whose multiplication is 21.
in another case where number is 4 there is only one prime number that is 2.
in this case 2 will be multiplied by 2 and there multiplication is 4 equals to the given number.
-
if number itself is a prime number
than numbers are 1 and number
itself…**EXPLAINATION :**
you can get it by just taking the modulus of given number from the number which are greater than 1 and less than
the given number and after operations there answer should be zero.And calculate only those number which are prime number and there multiplication equal to given number.
21=two prime nos are 7 and 3
same for 4= two prime nos are 2 and 2
post your code related statements using code Sample/blockquote option.
I don’t think, it’s is a good approach to solve.Prime factorization can give you result in O(log N) time.
@ayushagg31: Can you prime factorize in (log N) time without applying sieve?
log(N) prime factorization is kind of an illusion. It hides the O(n) complexity of Sieve. If you know any logic of prime factorization in O(log N), then do let me know. I would also like to learn such an amazing algorithm.
You are asking a question in an answer! Also, please let me know the sqrt(N) prime factorization algorithm you are referring to? You could google prime factorization in log N, and you will see many implementations where prime factorization is achieved in log N time BUT after SIEVE which takes O(n).
Such logics are useful for query problems.
1 Like
My bad :(.I actually understand it wrong, it’s actually O(log N) after sieve.The thing is, I am very lazy, when it comes to calculating complexity, so didn’t cross check it.Pardon my mistake and pls, don’t kill me for that(just kidding).
I think its better to find prime factors of given number by prime factorization,compare to find all prime factors upto given number(seive method).Because time complexity of prime factoriazation-O(sqrtn) compared to second method-O(n)
for n=8
factors[0]=2
factors[1]=4(becoz at the end of for loop,n=4 which is >2)
so ur code first of all dont produces prime factors?
Sieve takes O(sqrt n) for prime factorization.so for one than one querry it will be O(nsqrt(n)).So @utkalsinha how o(n).Also i want to know that below given pseudocode by @divyansh_gaba is seive algorithm? Or seive is something else . And i notice there is word “precomputation” discussed always with seive ? What it means ?plz help me im newbie for these concept.
Sieve takes O(sqrt n) for prime factorization.so for one than one querry it will be O(nsqrt(n)).So @utkalsinha how o(n).Also i want to know that below given pseudocode by @divyansh_gaba is seive algorithm? Or seive is something else . And i notice there is word “precomputation” discussed always with seive ? What it means ?plz help me im newbie for these concept.