VPF::Факторизация - Форум программистов

Гость_Pupsik

Дата 16.1.2006, 16:47 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

В рамках всеобщей ежегодной факторизации вам дали задание - написать программу, которая факторизует (раскладывает на простые множители) натуральное число N (1<N<=10^12).

Входные данные
Во входном файле записано единственное число N.

Выходные данные
Первая строка выходного файла должна содержать количество различных простых делителей P числа N. Каждая из следующих P строк должна содержать два числа, разделенных пробелом, первое - простой делитель числа N, второе - его степень в разложении. Делители надо выводить по порядку убывания их степени, а при одинаковой степени - по порядку возрастания самих делителей.

Пример

Ввод

4

Вывод

1
2 2

Нужен код на Pascal.

SoWa

Дата 16.1.2006, 20:23 (ссылка)

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

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

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

И все варианты выдать?
Прогоняй брутфорсом.

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

Всем добра smile

Guest

Дата 17.1.2006, 10:08 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Или можно отдельно накать поиск простых чисел и делить твое число только на найденные простые числа. До корня из числа.

Illuminaty

Дата 17.1.2006, 15:57 (ссылка)

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

Загрузка ...

/*Антон Захаров*/

Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

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

алгоритм примерно такой:

Код


считываем число N;
a = 2;
пока N > 1 или a < N делаем 
начало
  если a - простое то делаем
  начало
    p = 0;
    пока остаток от деления N на a в степени p равен 0 делаем
    начало
       p = p + 1;
    конец
    если p > 0 то делаем
    начало
      выводим в файл a p
      N = N/(a^p);
    конец
    a = a + 1;
  конец
конец

Это сообщение отредактировал(а) Illuminaty - 17.1.2006, 15:58

poor_yorik

Дата 17.1.2006, 17:13 (ссылка)

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

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 148
Регистрация: 12.1.2005
Где: Общаги г. Киева

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

Ну на Паскале это примерно будет так. Это без использования длинной арифметики...

Код


readln(N);
writeln(1);
a:=2; 
while (a<=trunc(sqrt(n))) do
 begin
  inc(a); b:=0;
  while (n mod a = 0) do
    begin
     n:=n div a;
     inc(b);
   end;
   if (b>0) then writeln(a,' ',b);
end;
if n>1 then writeln(n,' ',1);

Остается к тому присобачить длиннуб арифметику. И Ок smile

Это сообщение отредактировал(а) poor_yorik - 17.1.2006, 17:17

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

Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай...

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