Делители целого числа

Пример 1. Найти все делители неотрицательного целого числа n.

Вариант 1.Самый простой способ решения – это проверить по очереди делимость числа n на каждое из чисел 1,2,3,..., n. Число операций можно сократить, доказав, что в интервале [n/2+1,n-1] делителей числа n нет.

#include <iostream.h>

main()

{ int n,d;

cin>>n;

for (d=1;d<=n/2;d++)

if(n%d==0)

cout<<d<<endl;

}

Вариант 2. Для нахождения делителей числа n, достаточно обнаружить делители не превышающие значения квадратного корня из числа n. Все остальные делители получаются в результате деления числа n на найденные делители.

#include <iostream.h>

main()

{ int n,d;

cin>>n;

for (d=1;d*d<n;d++)

if(n%d==0)

cout<<d<<", "<<n/d<<endl;

if(d*d==n)

cout<<d<<endl;

}

Пример 2. Найти наибольший делитель двух неотрицательных целых чисел.

Решение основано на алгоритме Евклида, многократно использующим целочисленную операцию деления с остатком:

n=q*m+r₀,

m=q₀*r₀+r₁,

r₀=q₁*r₁+r₂

_{..........................}

r_k-1=q_k*r_k+r_k+1,

...........

r_j-1=qj*rj,

где rj – наибольший общий делитель.

#include <iostream.h>

main()

{ long int n,m,r,tmp;

cin>>n>>m;

if(m>n)

{ tmp=m; m=n; n=tmp;}

while(m>0)

{ r=n%m; n=m; m=r; }

cout<<n;

}

Пример 3. Найти все простые числа, меньшие заданного натурального числа n.

Вариант 1.

Для решения задачи необходимо проверить имеют ли числа из заданного интервала делители, не превышающие значения квадратного корня из числа n.. Четные числа можно не рассматривать, поскольку они делятся на два.

#include <iostream.h>

main()

{ int d,k,n;

cin>>n;

cout<<1<<endl<<2<<endl<<3<<endl;

k=5;

while (k<=n)

{ for (d=2;d*d<=k && k%d!=0;d++)

;

if(d*d>k)

cout<<k<<endl;

k=k+2;

}

}