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