Privire de ansamblu asupra algoritmilor pentru găsirea și recunoașterea numerelor prime, informații despre aplicabilitatea acestora

Privire de ansamblu asupra algoritmilor pentru găsirea și recunoașterea numerelor prime, informații despre aplicabilitatea acestora. Kuritsyn Mihail Lyulkova Elena Sizov Ilya

Număr simplu Un număr prime este un număr natural care are exact doi divizori naturali: unul și el însuși. Numerele rămase, cu excepția unuia, se numesc numere compuse. Secvența numerelor prime începe după cum urmează: 2, 3, 5, 7, 11, 13, 17, 19, 23. 29, 31, ... 3

Algoritmi pentru găsirea numerelor prime Simple modalități de a găsi lista inițială a numerelor prime până la o anumită valoare dau. Sita de la Eratosthenes Resheto Sundarama Reheto Atkina 6

Algoritmul Eratosthenes sieve: Fie p = 2 (primul număr prime). Presupunând din p, pașii în p, traversați toate numerele de la 2p la n din listă. Găsiți primul număr care nu depășește valoarea p și aloca valoarea variabilei p la acest număr. Repetați pașii 3 și 4 până când p este mai mare decât n. Numerele simple: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Eritosthenes sieve Complexitatea algoritmului: 8 O (n 2. 2 (??))

Sursa Sundarama 9 Algoritmul: Toate numerele naturale de la 1 la N exclud toate numerele formulei i + j + 2ij (i = 1,2, ..., 2 + 1? 1 2; j = i, i + 1, .... 2 + 1). Fiecare dintre numerele rămase este înmulțită cu 2 și mărită cu 1. Secvența rezultată este toate prime impare în intervalul [1,2 N + 1]. i = 1, j = 1, ..., 6; i = 2, j = 1,2,3; Numere simple: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.

Sita Sundarama. Justificare Algoritmul funcționează cu numere naturale impare mai mari de 1, reprezentate ca 2m + 1, unde m este un număr natural. Dacă numărul 2m + 1 este compus, atunci el este reprezentat ca produs de două numere impare de cele mari, adică: 10 2m + 1 = (2i + 1) (2j + 1). unde i, j sunt numere naturale m = 2ij + i + j. Ce este echivalent: Dacă excludem toate numerele formularului 2ij + i + j din setul de numere întregi pozitive. atunci pentru fiecare dintre numerele rămase m numărul 2m + 1 trebuie să fie simplu. Dacă numărul 2m + 1 este simplu, atunci numărul m nu poate fi reprezentat în forma 2ij + i + j, și astfel m nu va fi exclus în cursul operării algoritmului.

Sieve Atkin Bazele algoritmului sită Atkin sunt cele trei teoreme standard ale teoriei numerelor elementare: 11 n - simplu dacă: 4. 2 +. 2 =. (N> 0> 0) n mod 4 = 1 n - un număr impar n este simplu dacă: 3. 2 +. 2 =. (N> 0> 0) n mod 6 = 1 n - un număr impar n este simplu dacă: 3. 2. 2 =. (N> 0> 0) n mod 12 = 11 n este un număr impar de 1. 2. 3.

Algoritmul Creați o sită (o matrice de potrivire cu numerele prime pentru toate numerele pozitive începând cu 2). Inițial, toate elementele sita sunt marcate ca compozite. Pentru fiecare număr n din sită. dacă restul divizării prin modul este 60: 1, 13, 17, 29, 37, 41, 49 sau 53 și n = 4 * x2 + y2, schimbați valoarea din sită în sens opus. Este egal cu 7, 19, 31 sau 43 și n = 3 * x2 + y2; pentru a schimba valoarea sităi la contrariul. Este egal cu 11, 23, 47 sau 59 și n = 3 * x2 - y2 pentru (x> y); pentru a schimba valoarea din sită la contrariul. (x și y sunt numere întregi, numere pozitive) Luați cel mai mic număr din sita marcată ca prime și marcați toate elementele sitului care sunt multiplii ai pătratului acestui număr prime ca compozit. Repetați pasul 3 12

Sieve Atkin Algoritmul are o complexitate asimptotică: 13. (Log log.) Și necesită următorul număr de biți de memorie: O (.1 2 + ?? (1))

Compararea algoritmilor pentru găsirea numerelor prime 14

Algoritmi pentru recunoașterea numerelor prime. Teste de simplitate Testul de simplitate este un algoritm care determină numărul simplu de un număr natural dat. O căutare a teoriei divizoarelor Testul lui Wilson Testul lui Pepin Testul lui Miller Testul Rabin al lui Agrawal-Kayala-Saxen 15

Căutarea divizorilor Căutarea divizoarelor este un algoritm pentru testarea simplității unui număr prin enumerarea completă a tuturor divizoarelor potențiale posibile. 16 Algoritm: Căutați toate întregi de la 2 la rădăcina pătrată a numărului n și calculați restul de împărțire n de fiecare dintre aceste numere. Dacă restul de împărțire cu un număr m este zero, atunci m este un divizor al lui n. În acest caz, fie n este declarat compozit, iar algoritmul termină lucrarea. Atunci când se ajunge la o rădăcină pătrată a lui n și n nu este redusă la oricare dintre numerele mai mici, n este declarată simplă.

Teorema lui Wilson teorema lui Wilson este o teoremă a teoriei numerelor, care afirmă că 17 p este un număr prim dacă și numai dacă (p.1)! + 1 este divizibil cu p

Test Fermat Pe baza teoremei Fermat, care afirmă: 18 Dacă p este un număr prime, atunci pentru orice număr întreg se menține o egalitate. 1 (1) (1) sau (.1 - 1) este împărțit în. divizibil. Pentru compusul p, adevărul despre egalitate este puțin probabil. Notă:

Testul lui Pepin Testul lui Pepin este un test de simplitate pentru numerele Fermat. Numărul fermei este numărul speciilor. = 2 2 1. - întreg, non-negativ. Numărul Fermat este simplu dacă și numai dacă. (.) /. (.). Până în prezent sunt cunoscute numai 5 numere Fermat: 3, 5, 17, 257 și 65537. 19

Testul lui Miller - testul lui Rabin Miller - Rabin - este un test polinomial probabilistic al simplității. Testul vă permite să determinați în mod eficient dacă un anumit număr este compus. Cu toate acestea, cu ajutorul lui nu se poate dovedi riguros simplitatea unui număr. 20 Martori de simplitate și teorema lui Rabin Fie m un număr impar mai mare decât 1. Atunci m-1 poate fi reprezentat ca: m-1 = 2. * t. unde t este impar întregul a, 1

Testul lui Miller - Algoritmul Rabin 21: Parametrul algoritmului Miller-Rabin este numărul de runde r. În fiecare rundă sunt efectuate următoarele acțiuni: Un număr aleatoriu a, 2

Testul Miller-Rabin Complexitatea algoritmului. 22 O (3.) Cu toate acestea, corectitudinea algoritmului nu este întotdeauna dovedită. Probabilitatea ca un număr compus să nu fie detectat într-un timp t, de obicei nu depășește.

Trimiteți-le prietenilor: