Welcher ist der schnellste Algorithmus zur Auffindung von Primzahlen?

Question

Welcher ist der schnellste Algorithmus, um Primzahlen mit C++ zu finden? Ich habe das Siebverfahren verwendet, aber ich möchte immer noch, dass es schneller wird!

Answer 1

#include 

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;

    cout << endl;

    system ("pause");
    return 0;
}

Answer 2

Ich weiß, es ist etwas später, aber das könnte für Leute nützlich sein, die von Suchen hierher kommen. Wie auch immer, hier ist etwas JavaScript, das darauf beruht, dass nur Primfaktoren getestet werden müssen, daher werden die zuvor generierten Primzahlen als Testfaktoren für spätere wiederverwendet. Natürlich werden zuerst alle geraden und Mod-5-Werte herausgefiltert. Das Ergebnis wird im Array P sein, und dieser Code kann 10 Millionen Primzahlen in weniger als 1,5 Sekunden auf einem i7-PC (oder 100 Millionen in etwa 20) berechnen. In C umgeschrieben sollte er sehr schnell sein.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

Answer 3

#include
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Geben Sie das obere Limit ein :";
    cin>>num;

    cout<<"Primzahlen bis "<