|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Program A2_17a; Var n,k:integer; begin readln(n); k:=2; while
(k*k<=n) do begin while (n mod k=0) do begin
write(k,' '); ;n:=n div k; end;
INC(k); end; if
(n>1) then write(n); writeln; readln; end. |
// Program A2.17a; #include <iostream>
using namespace std;
int main() { int n,
k=2; cin>>n;
while(k*k<=n) {
while(n%k==0){cout<<k<<" "; ;n=n/k;} k++; }
if(n>1)cout<<n;
cout<<endl; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Program A2_17b; Var n:integer;
k:integer=2; p:integer=2; begin readln(n);
; while(k*k<=n ) do begin while
(n mod k=0) do begin
write(k,' '); ;n:=n div k; end; if(k<5) then INC(k)
else begin k:=k+p; p:=6-p; end; end; if
(n>1) then write(n); writeln; readln; end. |
// Program A2.17b; #include <iostream>
using namespace std;
int main() { int
n,k=2,p=2;
cin>>n;
while(k*k<=n ) { while(n%k==0){cout<<k<<" "; n=n/k;}
if(k<5) k++; else
{k=k+p; p=6-p;} }
if(n>1)cout<<n;
cout<<endl; return 0; } |
Разложить натуральное число N на простые делители.
Для этой задачи мы также разработали две программы.
В программе 2.17а, начиная с k=2 (строка 6) выполняем: если число n делится на k, то выводим на экран это k и число n делим на k, то есть удаляем делитель k из числа – строка 10. Если не делится на k, то увеличиваем k на 1 (строка 11) и снова выполняем предыдущие действия. Алгоритм сводится к следующему: удаляем все делители 2, если они есть, Затем все делители 3, затем проверяем 4 ( все равно на 4 делиться не будет, так как делители 2, если они были, все удалены раньше). Затем 5, затем 6 (на 6 все равно не разделится, ведь делители и 2 и 3 ( если они были) были удалены на предыдущем этапе. Остаются только простые делители.
Программа 2.17b отличается от предыдущей тем, что проверяем деление не на все числа подряд, а только на «кандидаты» в простые числа, которые вычисляем по формуле 6*k +/- 1, как в предыдущей программе. Так как «кандидаты» в простые числа начинаются с числа 5, то в программе проверяются числа 2, 3, 4, а с 5 уже по формуле – строки 10 12.
