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

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

Форум программистов > Алгоритмы > Факторизация

Автор: Гость_Pupsik 16.1.2006, 16:47

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

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

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

Пример

Ввод

4

Вывод

1
2 2

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

Автор: SoWa 16.1.2006, 20:23

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

Автор: Guest 17.1.2006, 10:08

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

Автор: Illuminaty 17.1.2006, 15:57

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

Код


считываем число 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;
  конец
конец

Автор: poor_yorik 17.1.2006, 17:13

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

Код


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