Решето на Ератостен - прости числа
Съдържание
решето на Ератостен
прости естествени числа
Определен кръг въпроси, свързани главно с теорията на числата, се решават с т. нар. метод на решето.
Исторически той възниква при търсене на прости числа.
Едно естествено число, по-голямо от 1, се нарича просто число, ако се дели само на себе си и на 1.
Алгоритъмът решето на Ератостен носи името на видния учен от древността Ератостен - математик, географ и астроном.
решето на Ератостен
Използваният алгоритъм за намиране на всички прости числа от даден интервал чрез сито на Ератостен е следният.
Нарича се още решето, защото местата, където са изписани отделните прости числа, са били пробивани.
Да вземем материал от рода на хартията – пергамент.
Написват се всички естествени числа от 1 до даденото число. 1 не е просто число и се задрасква.
Търси се първото незадраскано число (в началото това е 2) и се задраскват всички след
него (по-големи от него), които то дели - в случая всяко второ число, всяко четно число.
След това отново се търси първото незадраскано число, по-голямо от откритото при
предишния етап (на втората стъпка това е 3) и се задраскват всички числа след
него, които то дели - всички естествени числа кратни на 3.
Алгоритъмът спира, когато вече не може да продължи, т.е. незадраскани числа вече няма.
Останалите незадраскани са именно търсените прости числа.
Описаният алгоритъм се нарича решето, т.к. местата на числата са били пробивани и в края на алгоритъма пергаментът прилича на решето, сито.
Следващата примерна програма дава решена задача за търсене на прости числа чрез алгоритъм сито на Ератостен:
#include<iostream>
using namespace std;
int main () //nachalo na programata
{
const int gran=1850;//trqbwa da ima dostaychno swobodna RAM
int mas[gran+1];//razmera na masiwa e s 1 po-golqm ot granicata
int i,styp,por,gor_gr;//deklarirane na promenliwite
cout<<"Syzdajte programa, koqto otpechatwa wsichki prosti estestweni \n";
cout<<"chisla i tehniq broj po dadena gorna granica chrez sito Eratosten. \n";
cout<<"Whodni danni: estestweno chislo za gorna granica. \n";
cout<<"Primer: 20 Izhod 2,3,5,7,11,13,17,19 - 8 broq\n";//w dejstwitelnost se tyrsqt wsichki prosti chisla ot 2 do gornata granica
cout<<"Wywedete gorna granica [600-1500]: ";cin>>gor_gr;
for (i=2; i<=gor_gr; i++) {mas[i]=1;}
//wshichki elementi w masiwa da sa 1 - nachalna inicializaciq
por=2;//trygwa se ot 2 i se zapylwa s 0 wseki element kraten na 'por' bez pyrwiq
do { //nachalo na cikyla
styp=2*por;//nomer na element (chislo), kojto she se zapylwa s 0
while (styp<=gor_gr) {mas[styp]=0; styp +=por;} //obhovdane sys stypka por
por++;//sledwashoto poredno estestweno chislo
}while(por<gor_gr);//kraj na cikyla
por=0;//inicializaciq - za opredelqne broq prosti chisla
for(i=0;i<gor_gr;i++)//ot interwala 2 do opredelenata granica
{ //pechat resheto, sito na Eratosten - broi samo nezadraskanite chisla
if(mas[i]>0) {cout <<i << " ";por++;}// prosti chisla
}
//kraj na cikyla za pechat prosti chisla
cout<<endl;
cout<<"Broqt prosti chisla ot interwala: [2.."<<gor_gr<<"] e: "<<por<<endl;
system("pause"); //zadyrva programata do natiskane na klawish ot klawiaturata
return 0;//oswobovdawa zaetite sistemni resursi
}//kraj na programa prosti chisla - sito na Eratosten
Начало на страницата
прости естествени числа
В криптирането намират широко приложение прости естествени числа.
Един от алгоритмите за проверка дали едно число е просто е, като се провери дали числото N се дели на някое просто число, по-малко от квадратния корен на числото N.
Ако не се дели на нито едно от тях, то е това просто число.
Тук ще разгледаме този алгоритъм - намира се най-близкото цяло число M до корен квадратен от въведеното естествено число N.
Последователно, чрез цикъл от 2 до M се търси дали N се дели на някое от числата в този интервал.
В приложената примерна програма се дава решена задача за проверка дали въведено число е просто:
#include <iostream>
#include <cmath>
using namespace std;
int prosto (unsigned long N)
{ double kor,P;
int k,i,br;
P=(double)N;
kor=sqrt(P);//she tyrsim w interwala 2 do koren kwadraten (sqrt) ot wywedenoto estestweno chislo
i=(int)kor; //celochislena stojnost na korena
br=0;//nachalna inicializaciq za broj deliteli
cout<<"Prowerqwam za deliteli ot interwala [2.."<<i<<"]:\n";
for ( k=2; k<=i; k++)
{ if (N % k == 0) {cout<<"Otkrit e delitel: "<<k<<endl; br++;}
}//for - ako samo se prowerqwa cikylyt se prekyswa s break
return br; //broj otkriti deliteli ot interwala
}// prosto chislo
int main()
{ unsigned long N;
int i;
char ose;
do {
cout <<"Wywedete estestweno chislo [11..10101]: "; cin>>N;
i=prosto(N);
cout<<"Wywedenoto chislo e ";
if (i) cout <<"systawno.\n"; else cout <<"prosto.\n";
cout<<"She wywevdate li drugi chisla <y/n>: ";cin>>ose;
} while (ose=='y');
system ("pause");
return 0;
}//kraj na programa prosto chislo
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
Начало на страницата
