Делители на естествени числа

Съдържание

делимост
прости делители - итерация
прости делители - рекурсия
брой и сума на прости делители
Съвършено число
Най-голям общ делител - Евклид
Най-малко общо кратно - Евклид
общ брой делители

делимост

Нека имаме две естествени числа 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 

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Начало на страницата

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: