Modalități de numărare a primelor fără limite

Bine, poate că nu ar fi trebuit să scap de această întrebare prea mult ... Am văzut postul pe cel mai eficient mod de a găsi primele 10000 primes . Căut toate căile posibile . Scopul este de a avea un magazin unic pentru teste de primalitate. Oricare și toate testele pe care oamenii le cunosc pentru găsirea numerelor prime sunt binevenite.

Așadar:

  • Care sunt toate modalitățile diferite de a găsi primii?
0
fr hi bn
Rețineți că puteți număra numărul primelor de sub n fără a le calcula pe toate: en.wikipedia.org/wiki/…
adăugat autor Jeffrey Bosboom, sursa

8 răspunsuri

Un student de gradul Rutgers a găsit recent o relație de recurență care generează primesieri a>. Diferența dintre numerele sale succesive va genera fie prime, fie 1.

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)). 

Ea face o mulțime de prostii care trebuie să fie filtrate. Benoit Cloitre are, de asemenea, această recurență care are o sarcină similară:

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

atunci raportul dintre numerele succesive, minus un [b (n) / b (n-1) -1] este prime. Un cont complet al tuturor acestor lucruri poate fi citit la Recursivitate .

Pentru sită, puteți să faceți mai bine utilizând o roată în loc să adăugați o singură dată de fiecare dată, verificați Situri Incremental Incremental Prime Number . Iată un exemplu de roată. Să ne uităm la numerele 2 și 5 pentru a ignora. Roata lor este, [2,4,2,2].

0
adăugat

The Sieve of Eratosthenes is a decent algorithm:

  1. Take the list of positive integers 2 to any given Ceiling.
  2. Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.
  3. Repeat step two until you reach the given Ceiling.
  4. Your list is now composed purely of primes.

Există o limită funcțională a acestui algoritm prin aceea că schimbă viteza pentru memorie. Atunci când se generează liste foarte mari de prime, capacitatea de memorie necesită o creștere rapidă.

0
adăugat
detaliul crucial lipsește aici: cum găsești și cum elimini multiplii. Dacă le găsiți într-un mod corespunzător, adică numărați dintr-o primă în pașii acelui prim, nu le puteți elimina deloc , deoarece atunci nu puteți conta . Punctul spre SoE este marcarea multipli, folosind valorile ca adresele , fără compararea valorilor în complexitate). Acest lucru este exact ca ceea ce face ca numerele întregi să fie mai rapide decât cele de comparare. Ați renunțat la acest avantaj dacă le eliminați.
adăugat autor Will Ness, sursa

Pentru un număr întreg, cel mai rapid control de primalitate pe care îl știu este:

  1. Take a list of 2 to the square root of the integer.
  2. Loop through the list, taking the remainder of the integer / current number
    1. If the remainder is zero for any number in the list, then the integer is not prime.
    2. If the remainder was non-zero for all numbers in the list, then the integer is prime.

Utilizează o memorie mult mai mică decât Sieve of Eratosthenes și este în general mai rapidă pentru numerele individuale.

0
adăugat

@theprise

Dacă aș fi vrut să folosesc o buclă incrementală în loc de o listă instanțiată (probleme cu memorie pentru numere masive ...), care ar fi o modalitate bună de a face asta fără a construi lista?

Se pare că nu ar fi mai ieftin să efectuați o verificare a divizibilității pentru întregul dat (X% 3) decât doar verificarea numărului normal (N% X).

0
adăugat

Dacă doriți să găsiți o modalitate de generare a numerelor prime, acestea au fost acoperite într-un întrebarea anterioară .

0
adăugat

În algoritmul dvs. care utilizează lista de la 2 la rădăcina întregului, puteți îmbunătăți performanța prin testarea numai a numerelor ciudate după 2. Aceasta înseamnă că lista dvs. trebuie să conțină doar 2 și toate numerele impare de la 3 la rădăcina pătrată a întregului . Acest lucru taie de câte ori ați bucla în jumătate, fără a introduce mai multă complexitate.

0
adăugat

@ întrebarea lui akdom pentru mine:

Looping-ul ar funcționa bine pe sugestia mea anterioară și nu trebuie să faceți niciun fel de calcule pentru a determina dacă un număr este egal; în buclă, pur și simplu sări peste fiecare număr par, așa cum se arată mai jos:

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}
0
adăugat

Unele teste primare lucrează numai cu anumite numere, de exemplu, Lucas? Lehmer? / / Lucas? Lehmer a> test funcționează numai pentru numerele Mersenne.

Cele mai multe teste primare folosite pentru numerele mari pot să vă spună doar că un anumit număr este probabil "prime" (sau, dacă numărul nu reușește testul, este cu siguranță nu ). De obicei, puteți continua algoritmul până când aveți o probabilitate foarte mare ca un număr să fie prime.

Priviți această pagină și în special secțiunea "A se vedea de asemenea".

Testul Miller-Rabin este, cred, unul dintre cele mai bune teste. În forma sa standard vă oferă primele probabile - deși sa demonstrat că dacă aplicați testul la un număr sub 3.4 * 10 ^ 14 și trece testul pentru fiecare parametru 2, 3, 5, 7, 11, 13 și 17, este cu siguranță prime.

Testul AKS a fost primul test determinist, dovedit, de tip polinomial general. Cu toate acestea, din câte știu, cea mai bună implementare se dovedește a fi mai lentă decât alte teste, cu excepția cazului în care intrarea este ridicol de mare.

0
adăugat