Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.
Входные данные
Натуральное число [latex]n[/latex]
Выходные данные
Все его простые делители напечатанные через пробел
Тесты
| входные данные | выходные данные |
| 2 | 2 |
| 7 | 7 |
| 50 | 2 5 5 |
| 169 | 13 13 |
| 583 | 11 53 |
| 2368 | 2 2 2 2 2 2 37 |
| 73890 | 2 3 3 5 821 |
| 885066 | 2 3 7 13 1621 |
| 6943960340 | 2 2 5 97 1787 2003 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <cmath> using namespace std; int main() { unsigned long long n; cin>>n; for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) { if ( n % i == 0 ){ std::cout << i << ' '; n /= i; } else{ ++i; } } if ( n > 1 ) std::cout << n; return 0; } |
Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.
Ссылки
- Условие задачи(страница 135)
- Код на ideone
— Отступы!
— Для компилятора на IDEone.com максимальное число для выбранного вами типа данных ULLONG_MAX = 18446744073709551615 (2^64-1). Корень из этого числа почти 4294967296. А в переменную int поместится не боле чем INT_MAX = 2147483647. Это означает, что для ряда квадратов больших простых чисел цикл будет работать неверно. Например, Ваша программа зациклится для 18446744030759878681. А должно быть так.
Да и при исправлении этой ошибки вряд ли мы дождемся окончания работы Вашей программы для такого числа. Стоит глубже вникнуть в алгоритмы факторизации. Их вообще много и до сих пор не знают найдет ли лучший (самый быстрый).
Добавьте, пожалуйста предложенный мной тест и добейтесь, чтобы программа его прошла.
Исправил ошибку типа данных. Пройти тест так и не смог, хоть и ознакомился с алгоритмами факторизации.
К сожалению, я не смог их грамотно запрограммировать либо найти достойную реализацию.
Жаль. Первое улучшение в два раза можно сделать если заметить, что кроме двойки простых четных чисел нет.
Ладно. Хоть отступы сделайте и используйте sqrtl().