Algoritmi → Găsirea numerelor prime
Deoarece îmi place să rezolv diverse probleme matematice (projecteuler.net, diofant.ru.), Este întotdeauna necesar să facem aceleași acțiuni. Prin urmare, am creat un blog "Algoritmi", în care voi scrie periodic funcții pentru rezolvarea diferitelor probleme. Cred că mulți vor fi folositori.
Cei interesați pot, de asemenea, să împărtășească experiența lor. Legăturile cu alte resurse nu trebuie să fie aruncate, oricine dorește, el va găsi prin intermediul motoarelor de căutare. Sunt un amator C ++, deci toată sintaxa va fi pe ea.
Un număr prime este un număr care este împărțit fără restul numai de unul și de el însuși.
Prima funcție verifică dacă un număr este prime. Pentru a face acest lucru, trebuie să apelați funcția, trecând un număr pe care trebuie să-l verificăm pentru simplitate.
A doua funcție găsește următorul număr prime după numărul pe care îl transmitem în argumentele funcției.
Important! În ambele funcții, verificăm pentru restul când divizăm numărul dorit din cele două (deoarece acesta va fi divizibil cu 1) la rădăcina numărului nostru. Aceasta este o optimizare importantă a codului nostru, care ne permite să lucrăm cu numere mari. Fără aceasta, căutarea unei valori poate încetini semnificativ.
Și dacă rescrieți algoritmul în codurile mașinii? ) Și ar fi interesant să măsurați cât de mult va crește productivitatea.
Și dacă rescrieți algoritmul în codurile mașinii? ) Portabilitate și întreruperi de coduri de tip cross-platform.
Ei bine, acest lucru nu este adevărat. Tocmai vorbesc despre scrierea unui cod pentru un anumit procesor pentru a obține performanța maximă posibilă. Algoritmul este simplu și poate fi rescris pentru diferite sisteme de comandă, nu va fi.
Pentru spectacolul pe care îl scriu în articolul de mâine :)
Mulțumesc, faceți o treabă utilă.
În principiu, puteți păstra în continuare o listă cu numerele prime și divizibilitatea pentru a le verifica. Deoarece dacă un număr nu este divizibil printr-un singur număr prime, atunci este și simplu.
Acest lucru va accelera în special algoritmul pentru numerele mari. toate numerele mari de numere vor fi sărite
Știu această proprietate :)
Ei bine, nu știu cum să o pun în aplicare pe scurt și în mod clar. În viitor, sper, voi corecta acest lucru
De exemplu, creați o listă în care să scrieți toate numerele prime găsite. Și înlocuiți starea ciclului cu:
Sintaxa este mai degrabă C #, dar esența pare să treacă. Lista este o listă și rămâne doar să introduceți adăugarea următorului număr prime. Acest lucru este deja la gust sau înainte de întoarcere sau chiar când utilizați funcțiile
Voi experimenta, văd cum se justifică ea însăși :)
Din experiența mea, există 2 practici identice în mod rapid de a găsi primele câteva milioane de prime numere:
1. sita lui Eratosthenes,
2. verificarea divizibilității numerelor impare de numerele prime deja găsite (până la rădăcina pătrată a numărului testat).
În măsura în care înțeleg esența acestor metode este aceeași, doar abordarea din diferite părți. Și așa se pare că sita lui Eratosthenes ar trebui să consume mai multă memorie. necesită o gamă preliminară de toate numerele mai mică decât maximul necesar.
Ie pentru că s-ar găsi toate numerele prime până la un milion, avem nevoie de o serie de 999 999 numere de la 2 la 1 milion, iar în cazul divizibilitatea numerelor matrice va consta doar din numere prime
Sau există o implementare a unor site care nu consumă memorie?
Pentru site, puteți utiliza un bitmap. Munca va fi mai lentă, dar nu știu cât de lent.
1. Sita se concentrează pe un număr mare de operații simple (adăugiri)
2. A doua metodă se concentrează pe un număr mic de operații lente (împărțirea cu restul).
în sensul de a număra 1 într-un bit ca un exponent al unui număr prime, și 0 nu este, și apoi folosind un număr de biți în matrice pentru a determina numărul?
Pentru a spune adevărul, nu a funcționat cu bitmap-uri și este greu să dai seama cum se va realiza acest lucru, dar ideea de a transfera această rețea sub forma unei imagini (bitmap) este destul de interesantă))
Scrieți o unitate la bitul i al matricei a. constând din numere pe 32 de biți:
Cititul nu este mai greu. Apropo, puteți verifica 32 de numere pentru simplitate la un moment dat, comparând celula corespunzătoare a matricei a cu 0xffffffff.
Ar fi mult mai interesant să traducem algoritmul în algebra binară. Apoi puteți optimiza cât mai mult posibil toate operațiile. Procesoarele moderne au extins comenzi matematice, care ar putea fi utilizate pentru a ocoli compilatoarele universale. I când de mult timp a făcut ceva similar pentru sistemul de comenzi x86. Dar implementarea acestui lucru pe sistemul de comandă intel64 ar fi mult mai interesantă.