VPF::[C++] Задача с простыми множителями

Bishep

Дата 16.11.2009, 21:03 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите написать программу, которая бы для введенного натурального числа N
(1 < N <=1000000000) выводила список его простых множителей с учетом их кратности. Простые множители с учетом их кратности должны выводиться в виде пар n m (где n – количество множителей, m – значение множителя) в порядке возрастания значений множетелей.

kamre

Дата 17.11.2009, 01:41 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


#include <iostream>
#include <map>

using namespace std;

typedef map<long, long> factors;

void factorize(long n, factors & f)
{
    f.clear();
    long l = 2, r;
    while (l * l <= n) {
        while ((r = n % l) == 0) {
            f[l]++;
            n /= l;
        }
        if (l > 2)
            l += 2;
        else
            l = 3;
    }
    if (n > 1)
        f[n]++;
}

long multiply(const factors & f)
{
    long res = 1;
    factors::const_iterator iter;
    for (iter = f.begin(); iter != f.end(); ++iter) {
        for (int i = 0; i < iter->second; ++i) {
            res *= iter->first;
        }
    }
    return res;
}

void print(const factors & f)
{
    factors::const_iterator iter;
    for (iter = f.begin(); iter != f.end(); ++iter) {
        cout << iter->first;
        if (iter->second > 1)
            cout << "^" << iter->second;
        cout << endl;
    }
    cout << "product = " << multiply(f) << endl;
}

int main()
{
    factors f;
    factorize(1024 * 27 * 5 * 49 * 101, f); // 2^10 * 3^3 * 5 * 7^2 * 101
    print(f);
    factorize(23456789, f); // prime
    print(f);
    return 0;
}

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