c#-4.0 - 降低筛法寻找素数的时间复杂度

Question

请考虑以下代码

public void printSievePrimes()
        {
            int[] temp = new int[count];
            for (int j = 2; j * j < temp.Length; j++)
            {
                for (int i = j * j; i < temp.Length; i += j)
                {
                    primesFound[i] = false;
                }
            }
            for (int i = 2; i < temp.Length; i++)
            {
                if (primesFound[i] != false)
                    Console.WriteLine("PrimeFound is:" + i);
            }

        }

上述方法称为筛素数法，它是这样的；

1 从 2 开始并取消它的后续因素，如 4,6,8...

2 从 3 开始并抵消它后续的因素，如 9,12,15...

3 4..已经取消了

4 从 5 开始......以此类推

我已经做到了并且效果很好。但是想减少 它的复杂度为 O(n) 或 O(nlogn) 可以做什么？另一个问题是我必须遍历数组以获得最大的素数有没有办法找到使用有效方法找到的最大素数？

Answer 1

您发布的算法复杂度为 O(N log(N))。尽管通过此更改您可以稍微加快速度......我不知道它是否会提高算法的复杂性(可能会)

for (int j = 2; j * j < temp.Length; j++)
{
   if (primesFound[j] == false) continue;

   for (int i = j * j; i < temp.Length; i += j)
   {
      primesFound[i] = false;
   }
}

基本上...您发布的代码不会跳过数字 4，因为它从不检查该数字是否已被取消。