jhjfbsbfkbjfnfnfjfj's blog

Factors of product of two numbers
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

if x and y are two numbers ( >=1 && <= 1e9 ) how do i find all the factors of x*y in 1 second? Please help sample input : 158260522 200224287

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There will not be more than 8 unique prime factors each for x and y. You can easily enumerate them by trial division.

Now, combine the list of prime factors (removing duplicates). Now, multiply the prime factors together with different combinations of powers for each prime factor.

→ Reply