Two prime numbers

general
,
1

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*2
2

21=two prime nos are 7 and 3
same for 4= two prime nos are 2 and 2

3

post your code related statements using code Sample/blockquote option.

4

I 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])
5

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
6

I don’t think, it’s is a good approach to solve.Prime factorization can give you result in O(log N) time.

7

@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.

8

@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

9

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
10

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).

11

Thanks, @utkalsinha for correcting me and Sorry @vishesh_345 for my innocent mistake.

12

http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ prime factorisation in sqrt(n)

13

@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 :slight_smile:

1 Like
14

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)

15

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?

16

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.

17

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.

18

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

2 Likes
19

Then every concept discussed is related to other problem.plz dont blame anyone like this.

20

no bro , this was a direct question , you asked the query directly :slight_smile: . this is serious cheating if such is the case i will want the link to the question please

2 Likes