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

Разложение числа на простые делители
Автор so_close, история, 7 лет назад, По-русски

Всем добрый день! Возникла такая задача: для каждого 1 <= N <= 1 000 000, найти все простые делители. Находить степени этих самых простых делителей необязательно. Есть подозрение, что можно использовать решето Эратосфена и какой-то вспомогательный массив, но не могу завершить размышления. Может это и известная задача, не знаю. Кто поможет?

UPD. Следущий алгоритм медленный: делаем решето Эратосфена, потом проходимся по простым числам и проверяем деление. Разложение за O(sqrt(N)) медленное.

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

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

Если я правильно понял задачу, то достаточно быстро получать факторизацию. Этого можно добиться с помощью преподсчета минимального простого делителя. E-maxx

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Есть подозрение, что не поместится в память. Но скорее всего это то, что нужно. Спасибо!

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится 
vector<int> divs[1e6 + 1];

for (int i = 2; i <= 1e6; i++)
    if (divs[i].size() == 0)
        for (int j = i; j <= 1e6; j += i)
            divs[j].push_back(i);

Как-то так :)

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

Sieve of Erathostenes. Whenever you find a prime p, mark all numbers kp as divisible by it. You can't do any better, since this runs in O(size of your output).

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

Are you required to explicitely factor all of numbers in 1..N?

The most suitable solution seems to be here.

For those who don't speak Russian: lp is lowest prime factor and pr is with the prime numbers, everything else should be clear from the code.

→ Ответить