Задача на Си разложить на простые множители

[Yacub]

Нужно разложить число с количеством до ста символов на простые множители, например число:
93286507371999205962977351361478938 82665803050839205919257403713922543 17064584855785088915745761
Результат:
Простые множители: 995663^8 x 995669^8

[p51x]

Если бы это была такая простая задача, не было б ассиметричной криптографии. Есть несколько алгоритмов, но пребирать их долго.

[ura_111]

Да, это правда.
Посмотри ознакомительные видеоролики на эту тему. Ну, сами ролики длинные (по полтора часа идут) а тебе надо только небольшие фрагменты.

с 38:36 мин по 40:50 мин
https://www.youtube.com/watch?v=WiOnBj9gMG4

с 44:59 мин по 46:25 мин
https://www.youtube.com/watch?v=M5FkMt0KZZU


Если не секрет, а зачем это тебе?

[Yacub]

Сообщение от ura_111

Да, это правда.
Посмотри ознакомительные видеоролики на эту тему. Ну, сами ролики длинные (по полтора часа идут) а тебе надо только небольшие фрагменты.

с 38:36 мин по 40:50 мин
https://www.youtube.com/watch?v=WiOnBj9gMG4

с 44:59 мин по 46:25 мин
https://www.youtube.com/watch?v=M5FkMt0KZZU


Если не секрет, а зачем это тебе?

Задание в университете, суть в том что простые числа будут не больше 10^6, но как сделать чтоб программа воспринимала числа в которых до ста символов, я не представляю

[FPaul]

Если это лаба, то достаточно показать алгоритм и продемонстрировать его на сравнительно небольшом числе. Нужно только длинную арифметику реализовать.

Если длинную арифметику не обязательно реализовывать (допустим, лаба не по алгоритмам, а по моделированию чего-то), то можно взять готовую библиотеку в виде DLL - "gmp.dll".

Если это более серьёзная лаба - к ней всегда прилагается методичка с описанием.

[ura_111]

Yacub, занести в программу очень длинное число - это не сложно. Я бы советовал использовать матрицу, а лучше вектор, целого типа (и конечно же я бы попробовал динамическое распределение памяти):

18.jpg


А дальше, естественно, нужна писать "специальные законы" обработки таких "чисел".

Хотя знаешь, на этом форуме иногда вплывает данная тема (ты не первый) и если поискать, то возможно, можно чего-то и найти... Ну вот например (буквально вчера):

http://www.programmersforum.ru/showthread.php?t=298701

Правда там число представляли как строчку текста (когда будешь смотреть - обрати внимание на специально созданные "законы обработки").