Алгоритмы на С++
Решение задачи 5 главы 1
Как известно, каждое натуральное число \(n, n>1\), однозначно раскладывается в произведение простых сомножителей, например, \(13=13\), \(105=3\cdot 5\cdot 7\), \(72=2\cdot 2\cdot 2\cdot 3\cdot 3\). Разложите натуральное число на простые множители (факторизация числа).
Таблица простых чисел Что такое простое число
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
void prime_divisors(int n) { int t,k; cout<<n<<" ="; if (n<=1) { cout<<" "<<n; return ; } t=sqrt(n); k=2; //www.itmathrepetitor.ru while (k<=t) { if (!(n%k)) { n/=k; cout<<" "<<k; while (!n%k) { n/=k; cout<<" "<<k; } t=sqrt(n); } k++; }//www.itmathrepetitor.ru if (n>1) cout<<" "<<n<<endl; } |