Делители на естествени числа
Съдържание
делимост
прости делители - итерация
прости делители - рекурсия
брой и сума на прости делители
Съвършено число
Най-голям общ делител - Евклид
Най-малко общо кратно - Евклид
общ брой делители
делимост
Нека имаме две естествени числа N,M, където 1<M<N.
Под делимост ще разбираме алгоритъм, даващ еднозначен отговор дали числото N се дели без остатък на числото M без фактически да се извършва операцията делене.
Някои от тези правила са: делимост на 2: последната цифра на числото да е 0,2,4,6 или 8; делимост на 3: сумата от цифрите на числото да е кратна на 3; делимост на 4: число, съставено от последните две цифри от числото да е кратно на 4; делимост на 5: последната цифра на числото да 0 или 5, делимост на 6: сумата от цифрите на числото да е кратна на 3 и последната цифра да е четна, делимост на 8: число, съставено от последните 3 цифри на въведеното число да е кратно на 8 и др.
Нека разгледаме следната задача за делимост:
Имаме естествено число N от интервала [12..98]. От него се формира ново число M, чрез размяна местата на цифрите от числото N. Да се състави програма, чрез която се проверява дали:
а) сумата на двете естествени числа се дели без остатък на 11
б) разликата на двете естествени числа се дели без остатък на 9
Алгоритъм
За да формираме новото число трябва да намерим всяка от цифрите c1,c2 на въведеното число N.
Дясната цифра е c1 = N%10 – целочислено делене по модул; лявата цифра е c2=N/10 – целочислено делене. Новото число M = c1*10 + c2. С цел по-добро онагледяване се извършва размяна на стойностите, така че първото число да е по-голямо от двете. Извършваме последователно проверка за делимост от сумата (N+M)%11 и разликата (N-M)%9.
Следващата примерна програма дава решена задача за делимост:
#include <iostream>
using namespace std;
int main()
{int a,b,c,c1,c2;
cout<<"Imate estestweno chislo a ot interwala [12..98]. Ot nego se \n";
cout<<"formira nowo estestweno chislo b, s razmeni mesta na cifrite na chisloto a.\n";
cout<<"Da se systawi programa, chrez koqto se dokazwa a+b e kratno na 11\n";
cout<<"a-b e kratno na 9.\n";
cout<<"Wywedete dwucifreno estestweno chislo [12..98]: ";cin>>a;
a%=100;//walidizirane po whod za estestweno chislo
c1=a%10;//dqsna cifra
c2=a/10;//lqwa cifra
b=c1*10+c2;
cout<<" Nowoto estestweno chislo s razmenenite cifri e: "<<b<<endl;
if (a<b) {a=a+b;b=a-b;a=a-b;}// razmqna stojnosti chrez sybirane
c=a+b;
cout<<"suma: "<<a<<" + "<<b<<" = "<<c<<" %11= "<<(c%11)<<endl;
c=a-b;
cout<<"razlika: "<<a<<" - "<<b<<" = "<<c<<" %9 = "<<(c%9)<<endl;
system("pause");
return 0;
}//kraj na programata estestweno chislo
Начало на страницата
всички прости делители на естествени числа
Проверката за прости делители на множество числа налага използването на итерация / рекурсия за обхождане на всички естествени числа от интервала.
Всяка програма съдържаща цикличен алгоритъм може да се реализира, както с итерация, така и с рекурсия. Следващите няколко програми дават решение на задача търсене на делители, прости делители, брой прости делители на естествени числа от предварително указан числов интервал.
Тук целта е да се представят успоредно двата варианта.
прости делители - итерация
Задачата е следната: търсят се всички прости делители на всяко отделно естествено число, принадлежащо на даден затворен числов интервал.
Всяко естествено число се дели на 1 и на себе си. Така простите естествени числа имат само 2 възможни делителя, а съставните повече.
Интуитивният подход за определяне вида прости делители на едно естествено число N се състои в проверка дали всяко от числата, принадлежащи на интервала [2..N] се явява делител на числото N.
Ако е открит делител на това число, то числото се дели с простия делител и се проверява дали същият прост делител не се повтаря в полученото ново по-малко естествено число.
Следващата примерна програма дава решение на задача - прости делители на естествено число чрез итерация:
#include<iostream>
#include<cmath>
using namespace std;
void deliteli_I(int p, int k)
{ while(p!=1)
{ if(p%k==0)
{cout<<k<<" ";p=p/k;}//prodylvawa tyrsene sys syshiq delitel
else k++;//tyrsene za delimost sys sledwashoto estestweno chislo
}//while
}// prosti deliteli na estestweno chislo - iteraciq
int main()
{
int Min, Max, M,N,i,k=2;
cout<<"Imate wywedeni 2 estestweni chisla M,N, opredelqshi zatworen\n";
cout<<"chislow interwal. Chislata M,N sa razlichni i sa w interwala[5..105].\n";
cout<<"Da se systawi programa izwevdasha wsichki prosti deliteli\n";
cout<<"na chislata ot zatworeniq interwal [M..M], kydeto M<N.\n";
cout<<"Wywedete nachalo na interwala N = "; cin>>N;
cout<<"Wywedete kraj na interwala M = "; cin>>M;
//zashita po whod za opredelqne nachalo - kraj na prowerqwaniq interwal
Min=(N+M - abs(N-M))/2;//nachalo na interwala
Max=(N+M + abs(N-M))/2;//kraj na interwala
//cikyl za obhovdane wsichki estestweni chisla ot interwala [M..N]
for(i=Min;i<=Max;i++)
{cout<<"chisloto: "<<i<<" ima deliteli ";
deliteli_I(i,k);//prowerka za delimost s nachalo 2
cout<<endl;
}//for
system ("pause");//chaka natiskane na klawish
return 0;//wrysha kod na greshka
}//kraj na programa deliteli na estestweni chisla
Начало на страницата
прости делители - рекурсия
Проверката за прости делители на множество числа налага използването на итерация / рекурсия за обхождане на всички числа от интервала.
Всяка програма съдържаща цикличен алгоритъм може да се реализира, както с итерация, така и с рекурсия.
Тук целта е да се представят успоредно двата варианта.
Следващата примерна програма дава решение на задача - прости делители на естествени числа чрез рекурсия:
#include<iostream>
#include<cmath>
using namespace std;
void deliteli_R(int p,int k)
{ if (p!=1)//uslowie za kraj - dokato chisloto e <>1
{if(p%k==0) {cout<<k<<", ";p=p/k;} //otkrit e delitel
else k++;//rekursiqta prodylvawa s delitel sledwashoto estestweno chislo
deliteli_R(p,k);//rekursiwno izwikwane
}//if
}// prosti deliteli na estestweno chislo
int main()
{
int Min, Max, M,N,i,k=2;
cout<<"Imate wywedeni 2 estestweni chisla M,N, opredelqshi zatworen\n";
cout<<"chislow interwal. Chislata M,N sa razlichni i sa w interwala [5..105].\n";
cout<<"Da se systawi programa izwevdasha wsichki prosti deliteli\n";
cout<<"na chislata ot zatworeniq interwal [M..M], kydeto M<N.\n";
cout<<"Wywedete nachalo na interwala N = "; cin>>N;
cout<<"Wywedete kraj na interwala M = "; cin>>M;
//zashita po whod za opredelqne nachalo - kraj na prowerqwaniq interwal
Min=(N+M - abs(N-M))/2;//nachalo na interwala
Max=(N+M + abs(N-M))/2;//kraj na interwala
//cikyl za obhovdane wsichki chisla ot interwala [M..N]
for(i=Min;i<=Max;i++)
{cout<<"Chisloto: "<<i<<" ima deliteli ";
deliteli_R(i,k);//prowerka za delimost s nachalo 2
cout<<endl;
}//for
system ("pause");//chaka natiskane na klawish
return 0;//wrysha kod na greshka
}//kraj na programa deliteli na estestweni chisla
Начало на страницата
брой и сума на прости делители
Да разгледаме следната задача: има въведено естествено число N от интервала [4..10004]. Търсим брой и сума на всички прости делители за числата от интервала [2..N]. Нека припомним, че всяко просто число има за делители 1 и самото число.
Използван алгоритъм:
В цикъл проверяваме кои числа са прости делители последователно за всяко едно от числата в интервала [2..N].
Ако е открит прост делител делим числото на него и проверяваме дали това естествено число не се дели отново на същия делител - пример 8 има прост делител 2 - 8=2*2*2
В приложената програма е даден пример с 6
2 - прост делител 2
3 - прост делител 3
4 - прости делители 2,2
5 - прост делител 5
6 - прости делители 2,3
Общ брой на всички прости делители 1+1+2+1+2 = 7
Общата сума на всички прости делители е: 2+3+2+2+5+2+3 = 19
Следващата примерна програма дава решение на задача за брой и сума на всички прости делители на естествено число:
#include <iostream>
using namespace std;
unsigned long suma_prosti_deliteli (int koe, unsigned long &broi )
{ int j;
unsigned long suma=0;
for (j=2;j<=koe;j++)
{ while (!(koe%j)) //k % j ==0 delenie bez ostatyk
{broi++;// nameren e prost delitel
suma+=j;// uwelichawa se sumata sys syotwetniq delitel
cout<<j<<endl;//izwevda prostiq delitel
koe/=j;//deli towa estestweno chislo na otkritiq prost delitel
} // while dokato towa chislo oshe se deli bez ostatyk
}//for j
return suma;
}//
int main ()
{ int N,i;
unsigned long sum, broi;
char ose;
cout<<"Imate wywedeno estestweno chislo N ot interwala [4..10004].\n";
cout<<"Tyrsim broj i sumata na wsichki prosti deliteli ot interwala [2..N].\n";
cout<<"Primer: 6 Izhod broi 7, suma 19 \n";
do {
broi=sum=0;//nachalna inicializaciq
cout<<"Wywedete estestweno chislo N [2..10001]: ";cin>>N;
for (i=2;i<=N; i++) //wsichki chisla se delqt na 1
{ cout<<"Za chisloto "<<i<<" prostite deliteli sa:"<<endl;//porednoto chislo
sum+=suma_prosti_deliteli(i,broi);
}//for i
cout<<"Obsh broj na wsichki prosti deliteli: "<<broi<<endl;
cout<<"Obsha suma na wsichki prosti deliteli: "<<sum<<endl;
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y');
system("pause");
return 0;
}//kraj na programata prosti deliteli na estestweno chislo
Начало на страницата
Съвършено число
В математиката и информатиката под съвършено число се разбира естествено число,
което може да се представи като сума от всички свои делители (без самото число).
Описанието включва за делител и 1. Всички познати до момента съвършени числа са четни.
От античността са познати първите 4 съвършени числа: 6, 28, 496 и 8128.
Тези числа са описани от Евклид в съчинението си "Елементи".
Той е използвал формулата за търсене на мерсенови числа (2^(n-1))*(2^n -1).
Пример 496 = (2^4 )*(2^5 -1) = 16 * 31.
Някои от тези числа имат симптоматична роля в организацията на социалния живот – 6 работни дни от седмицата, 28 е близко до продължителността на лунарния месец.
Няколко примера за съвършени числа и техните делители – естествени числа:
6 = 1 + 2 + 3;
28 = 1 + 2 + 4 + 7 + 14
Петото съвършено число е 33 550 336. Следващите съвършени числа нарастват много бързо и надхвърлят допустимите размери за цели числа в езиците за програмиране.
#include <iostream>
using namespace std;
int long sywyrsheno_deliteli (long chislo )
{ int j;
long suma=0;//nachalna inicializaciq na suma
for (j=1;j<chislo;j++)
{ if (!(chislo%j)) //chislo % j ==0 delenie bez ostatyk
{// nameren e poreden delitel na towa estestweno chislo
suma+=j;// uwelichawa se sumata s nowiq delitel
cout<<j<<endl;//izwevda poredniq delitel
} // while dokato chisloto oshe se deli bez ostatyk
}//for j
cout<<"Suma na delitelite: "<<suma<<endl;
return chislo-suma;
}//
int main ()
{ long N, dali;
char ose;
cout<<"Imate wywedeno estestweno chislo N ot interwala [4..10004].\n";
cout<<"Tyrsim sumata na wsichki negowi deliteli ot interwala [1..N-1].\n";
cout<<"Primer za sywyrsheni chisla: 6, 28, 496, 8128, 33550336. \n";
do {
cout<<"Wywedete estestweno chislo N [2..10001]: ";cin>>N;
cout<<"Za chisloto "<<N<<" deliteli sa:"<<endl;//porednoto chislo
dali=sywyrsheno_deliteli(N);
if (dali) cout<<"Wywedenoto chislo ne e sywyrsheno!\n";
else cout<<"Wywedenoto chislo e sywyrsheno.\n ";
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y');
system("pause");
return 0;
}//kraj na programata sywyrsheni chisla
Начало на страницата
общ брой делители
Имаме естествено число N, което е съставно.
Можем да определим всички негови делители с последователна проверка за делимост в интервала за всички естествени числа [2..N],
или да изведем само неговите прости делители. Нека простите делители да са числа от редицата естествени числа a1, a2, ...am.
Броят на всички делители се определя от произведението K = (a1 + 1)*(a2 + 1)*(a3 + 1)*…*(am + 1).
Следващата примерна програма илюстрира двата алгоритъма за намиране на общ брой делители:
#include <iostream>
using namespace std;
int const N=10000;//maksimalnoto chislo
int deliteli_1(int ch)
{ int i,j=0;
for(i=1; i<=ch; i++)
{ if (ch%i==0) j++; } //for izcherpwsho tyrsene na deliteli
return j;
} //deliteli
int deliteli (int ch, int mas[])
{int i,k,j=ch;
//startira inicializaciq na masiwa s broj i wid deliteli
for (i=0;i<N;i++){ mas[i] = 0;}//nachalna inicializaciq
i=1;//nachalen delitel
while (ch>1)
{ i++;
while (ch%i==0)
{mas[i]++;//uwelechawa s edinicia broq deliteli ot tozi wid
ch/=i; //deli chisloto s tozi delitel
}// dokato promenliwata i e delitel
}//while ch
k=1;
for (i=2;i<j;i++)
{ if (mas[i]>0)
{k=k*(mas[i]+1);}//kombinacii ot deliteli
}
return k;
}// deliteli
int main()
{int mas[N], broi, ch;
char ose;
cout<<"Imate estestweno chislo N ot interwala [2..10000]. \n";
cout<<"Tyrsim obshiq broj negowi deliteli - 1 i N sa sysho deliteli.\n";
cout<<"Primer 12 Izhod 6\n"; //1,2,3,4,6,12
do {
cout<<"Wywedete chislo: ";cin>>ch;
broi=deliteli (ch,mas);
cout<<"Broj kombinacii ot deliteli "<<broi<<endl;
cout<<"Izcherpwasho tyrsene na deliteli "<<deliteli_1(ch)<<endl;
cout<<"She drug prowerki za deliteli <y/n>: ";cin>>ose;
} while (ose=='y');
system("pause");
return 0;
}//kraj na programata deliteli na estestweno chislo
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
Начало на страницата