Improved Sieve of Eratosthenes

Name

Fork of Sieve of Eratosthenes

Prime numbers
Prime factorization

Edit

Comparing to classic sieve of Eratosthenes this algorithm has complexity O(n). Moreover, it computes minimal prime factor for each number in [2..N], but uses more memory.

C# Other implementations: Python

public class ImprovedSieveOfEratosthenes
{
    public static void Generate(int n, out int[] lp, out List<int> pr)
    {
        lp = new int[n];
        pr = new List<int>();
        for (var i = 2; i < n; i++)
        {
            if (lp[i] == 0)
            {
                lp[i] = i;
                pr.Add(i);
            }
            foreach (var prJ in pr)
            {
                var prIj = i * prJ;
                if (prJ <= lp[i] && prIj <= n - 1)
                {
                    lp[prIj] = prJ;
                }
                else
                {
                    break;
                }
            }
        }
    }
}