It's Algorithm Power
New
C#
C++
Java
JavaScript
PHP
Python
Ruby
More...
Save in fork
Save
Name
Fork of
Sieve of Eratosthenes
Prime numbers
Prime factorization
Huge
Normal
Small
Add
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
New implementation
C++
Java
JavaScript
PHP
Ruby
C
Clojure
More...
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; } } } } }