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

ma_lover

Дата 30.4.2007, 12:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 37
Регистрация: 24.3.2007

Репутация: нет
Всего: нет

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

HazzarD

Дата 30.4.2007, 12:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 30.4.2007

Репутация: нет
Всего: нет

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

Lomir

Дата 30.4.2007, 12:38 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 30.1.2007
Где: Lithuania::Kaunas

Репутация: нет
Всего: 1

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 30.4.2007

Репутация: нет
Всего: нет

у меня задача тоже есть про делители условие всей задачи по ходу решения возникла проблема - если есть массив степеней простых делителей некоего числа. как посчитать количество всех делителей этого числа, включая 1 и само число.

Lomir

Дата 30.4.2007, 18:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 30.1.2007
Где: Lithuania::Kaunas

Репутация: нет
Всего: 1

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

HazzarD

Дата 1.5.2007, 15:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 30.4.2007

Репутация: нет
Всего: нет

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

Artemios

Дата 1.5.2007, 16:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 1
Всего: 50

Цитата(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). И так далее.

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »