Finden Sie die 10001. prime

Question

nahm ich einen Blick auf die folgende Frage von Project Euler:

durch den ersten sechs Primzahlen Auflistung: 2, 3, 5, 7, 11 und 13 können wir, dass der 6. sehen Primzahl ist 13. Was ist die 10 001st Primzahl?

Ich habe versucht, die Quadratwurzel der Zahl zu nehmen und dann alle Primzahlen unter der Quadratwurzel der Zahl zu finden und dann die Zahl durch alle Quadratwurzeln zu teilen und zu sehen, ob jedes Mal 0 übrig ist. Wenn die Zahl nicht durch alle Primzahlen unter ihrer Quadratwurzel teilbar ist, ist sie eine Primzahl. Ich habe das getan, um die Iterationen zu reduzieren, die das Programm machen muss. Hier ist, was ich jetzt habe, ich bin mir nicht sicher, warum es nicht funktioniert. Weiß jemand, was ich falsch gemacht habe?

List<int> primeNumbers = new List<int>(); 
     bool prime = true; 
     bool MainPrime = true; 
     int check = 1; 
     for (long i = 3; i < long.MaxValue; i++) 
     { 
      if ((i % 2) != 0) 
      { 
       int root = Convert.ToInt32(Math.Sqrt(i)); 
       for (int j = 1; j < root; j++) 
       { 
        for (int k = 2; k < j; k++) 
        { 
         if ((j% k) == 0) 
         { 
          prime = false; 
         } 
        } 
        if (prime) 
        { 
         primeNumbers.Add(j); 
        } 
        prime = true; 
       } 

      } 
      foreach (var item in primeNumbers) 
      { 
       if ((i%item) == 0) 
       { 
        MainPrime = false; 
       } 
      } 
      primeNumbers.Clear(); 
      if (MainPrime) 
      { 
       check++; 
      } 
      if (check == 10001) 
      { 
       Console.WriteLine(i); 
       break; 

      } 
     } 

     Console.ReadKey(); 

Answer 1

Mehrere Punkte:

1. Wenn möglich Primteilern zu finden, müssen Sie alle Zahlen prüfen, bis zur Quadratwurzel enthalten, so dass sich Ihr Zustand j < root falsch ist.

2. Sie müssen die Primzahlen nicht erneut für jede Zahl neu berechnen. Behalten Sie die Liste bei und fügen Sie neue Primzahlen hinzu.

3. Sobald Sie einen Divisor finden, können Sie aus der foreach-Schleife ausbrechen.

Verbesserte Code:

List<long> primeNumbers = new List<long>() { 2 }; 
for (long i = 3; i < long.MaxValue; i += 2) 
{ 
    if(!primeNumbers.Any(p => (i % p) == 0)) 
    { 
     primeNumbers.Add(i); 
     if (primeNumbers.Count == 10001) 
     { 
      Console.WriteLine(i); 
      break; 
     } 
    } 
} 

Gibt 104743 als 10001. prime.