Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нахождение простых делителей

Автор: ma_lover 30.4.2007, 12:23

Подскажите пожалуйста какой-нибудь способ нахождения простых делителей числа N, пригодный для реализации в программе. Учитывая, что нет таблицы простых чисел и каждый раз N будет вводится новое.

Автор: HazzarD 30.4.2007, 12:32

проверяй от 2 до n/2 на делимость. усовершенствование - если до sqrt(n) нет делителей - число простое.
а вообще неплохо было бы указывать входные данные (диапазон значений n)...

Автор: Lomir 30.4.2007, 12:38

Поищи что нибуть по факторизации (если для больших чисел надо).
Вот самый простой алгоритм.

Код


std::vector<int> findPrimes(int a)
{
    std::vector<int> ret;
    for (int i = 2; i < int(sqrt(double(a)))+1; ++i)
        while (a % i == 0)
        {
            ret.push_back(i);
            a /= i;
        }
    if (a > 1) ret.push_back(a);
    return ret;
}

Автор: HazzarD 30.4.2007, 14:00

у меня задача тоже есть про делители http://acm.timus.ru/problem.aspx?space=1&num=1049 по ходу решения возникла проблема - если есть массив степеней простых делителей некоего числа. как посчитать количество всех делителей этого числа, включая 1 и само число.

Автор: Lomir 30.4.2007, 18:10

Предположим число X имеет вид:
2^a * 3^b * 5^c *7^d....
Тогда число делителей равно:
(a+1)*(b+1)*(c+1)*(d+1)....

Автор: HazzarD 1.5.2007, 15:03

а математический вывод этого?

Автор: Artemios 1.5.2007, 16:49

Цитата(HazzarD @ 1.5.2007, 16:03

)

а математический вывод этого?

Предположим, у тебя есть число 2^a.
Сколько у него делителей?
Все делители: 2^0=1, 2^1=2, 2^2, 2^3, ... 2^(a-1), 2^a .
Сколько их штук? Правильно, (a+1). И так далее.