1만1번째 주요

Question

찾기 내가 프로젝트 오일러에서 다음과 같은 질문을 살펴했다 2, 3, 5, 7, 11, 13, 우리는 6 것을 알 수 있습니다 프라임은 13입니다. 10 001 번째 소수는 무엇입니까?

숫자의 제곱근을 취하여 숫자의 제곱근 아래에있는 소수를 모두 찾은 다음 숫자를 모든 제곱근으로 나누고 매번 0이 남았는지 확인하려고했습니다. 숫자가 제곱근 아래의 모든 소수로 나눌 수없는 경우 소수입니다. 나는 프로그래머가해야하는 반복을 줄이기 위해 이것을했다. 여기에 제가 지금 가지고있는 것이 있습니다, 왜 그것이 작동하지 않는 것인지 확신 할 수 없습니다. 아무도 내가 뭘 잘못했는지 아니?

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

몇 가지 포인트 :

1. 가능한 주요 약수를 찾는 당신은 너무 당신의 상태 j < root가 잘못된, 이을 포함 제곱근까지의 모든 번호를 확인해야합니다.

2. 모든 숫자에 대해 다시 소수점을 다시 계산할 필요는 없습니다. 목록을 유지하면서 새로운 소수를 추가하십시오.

3. 제수가 발견되는 즉시 foreach 루프에서 벗어날 수 있습니다.

향상된 코드 :

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; 
     } 
    } 
} 

가 10,001번째 주요으로 104,743 제공합니다.