Eratosthenes最適化のふるい

Question

私は、Eratosthenesのふるいを使って2-nから素数を見つける独自のプログラムを作った。複合番号を削除するより効率的な方法を実装する方法はありますか？プロジェクトへ

リンク：https://github.com/Gurran/Sieve-of-Eratosthenes

class Program 
{ 
    static void Main() 
    { 
     int max; 

     Console.Write("Enter max number: "); 
     max = int.Parse(Console.ReadLine()); 
     FindPrimes(max); 
     Console.ReadLine(); 
    } 

    // Prints numbers. 
    public static void PrintMap(List<int> List) 
    { 
     for (int i = 0; i < List.Count; i++) 
     { 
      if (i % 10 == 0) 
       Console.WriteLine(); 
      Console.Write(List.ElementAt(i) + ", "); 
     } 
    } 

    // Generates list containing 2 - max 
    // Removes non-primes 
    // Calls PrintMap method 
    public static void FindPrimes(int max) 
    { 
     int x = 2; 
     List<int> NrRange = new List<int>(); 

     for (int i = 2; i < max; i++) 
      NrRange.Add(i); 
     for (int i = 0; i < NrRange.Count; i++) 

      for (int j = x; j < NrRange.Count; j++) 
       if (NrRange.ElementAt(j) % x == 0) 
        NrRange.RemoveAt(j); 
      x++; 
     PrintMap(NrRange); 
    } 
} 

Answer 1

私はFindPrimes(100)あなたのルーチンを実行したと私は間違っ結果持っている：

2、3、5、7、を、11,13,,17,19,,23,, .. 、97、

のは、いくつかの異なる方法でそれを書いてみましょう：

// If we put "FindPrimes", let's return them: List<int> instead of void 
public static List<int> FindPrimes(int max) { 
    if (max < 2) 
    return new List<int>(); 

    // Try avoid explict adding .Add(), but generating 
    List<int> result = Enumerable 
    .Range(2, max - 1) 
    .ToList(); 

    // sieving composite numbers out the initial list 
    for (int i = 1; i < result.Count; ++i) { 
    int prime = result[i - 1]; 

    // removing all numbers that can be divided by prime found 
    // when removing we should loop backward 
    for (int j = result.Count - 1; j > i; --j) 
     if (result[j] % prime == 0) 
     result.RemoveAt(j); 
    } 

    return result; 
} 

テスト

Console.Write(String.Join(", ", FindPrimes(100))); 

結果：

2、3、5、7、11、13、17、19、23、29、31、37、...、83、89、97