Блог пользователя jhjfbsbfkbjfnfnfjfj

Factors of product of two numbers
Автор jhjfbsbfkbjfnfnfjfj, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить