2-17r · informatik.az

Разложить натуральное число 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.

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;

}

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;

}