using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
public class Program
{
public static void Main()
{
var timer = new Stopwatch();
int n = 1_000_000_000;
timer.Restart();
Console.WriteLine("==== Sieve22Max_Basic ===");
var list = Sieve22Max_Basic(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");
Console.WriteLine();
timer.Restart();
Console.WriteLine("==== Sieve22Max_Enh ===");
list = Sieve22Max_Enh(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");
}
// this is basic Sieve of Eratosthenes
public static List<int> Sieve22Max_Basic(int n) {
var primes = new List<int>();
var sieve = new BitArray(n, true); // default all number are prime
//int crossTotal = 0;
int sqrt_n = (int)Math.Sqrt(n);
for (int p = 2; p < sqrt_n; ++p) {
if (sieve[p]) {
primes.Add(p);
//var cross = new List<int>();
int inc = p == 2 ? p : 2 * p;
for (int mul = p * p; mul < n; mul += inc) {
// cross out multiple of prime p
// cross.Add(mul);
//++crossTotal;
sieve[mul] = false;
}
//if (cross.Count > 0)
// Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
}
}
//Console.WriteLine($"crossTotal: {crossTotal:n0}");
for (int p = sqrt_n; p < n; ++p)
if (sieve[p])
primes.Add(p);
return primes;
}
public static List<int> Sieve22Max_Enh(int n) {
var sieve = new BitArray(n, true);
var spd = new int[n];
for (int i = 0; i < n; ++i) spd[i] = i;
var primes = new List<int>();
//int crossTotal = 0;
int sqrt_n = (int)Math.Sqrt(n);
for (int p = 2; p < sqrt_n; ++p) {
if (sieve[p]) {
primes.Add(p);
//var cross = new List<int>();
int inc = p == 2 ? 1 : 2;
for (long mul = p; mul * p < n; mul += inc) {
if (spd[mul] >= p) {
sieve[(int)(mul * p)] = false;
spd[mul * p] = p;
//++crossTotal;
//cross.Add((int)(mul * p));
}
}
//if (cross.Count > 0)
// Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
}
}
//Console.WriteLine($"crossTotal: {crossTotal:n0}");
for (int p = sqrt_n; p < n; ++p)
if (sieve[p])
primes.Add(p);
return primes;
}
}
