Geek asks and answers

Reducing the time complexity of the sieve

Please consider the following code

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

        }

The above method is called the sieve method of finding prime numbers. It looks like this:

1 start at 2 and cancel it subsequent factorists like 4,6,8 ...

2 start with 3 and cancel its subsequent factors, such as 9,12,15 ...

3 4 .. already canceled

4 starts with 5 ... and so on

I did this and it works well. But I want to reduce this complexity for O (n) or O (nlogn). What can be done? Another problem is that I need to iterate over the array to get the largest prime, is there a way to find the largest prime found using the efficient method?

+3
source share
1 answer

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, , .

+1

More articles:


All Articles