/* 
 * Variants of the sieve of Eratosthenes (C#)
 * by Project Nayuki, 2016. Public domain.
 * https://www.nayuki.io/page/the-versatile-sieve-of-eratosthenes
 */

using System;


public sealed class EratosthenesSieves {
	
	// Given an integer limit, this returns a list of Booleans
	// where result[k] indicates whether k is a prime number.
	public static bool[] SievePrimeness(int limit) {
		if (limit < 0 || limit == int.MaxValue)
			throw new ArgumentOutOfRangeException("Limit out of range");
		bool[] result = new bool[limit + 1];
		for (int i = 2; i < result.Length; i++)
			result[i] = true;
		for (int i = 2, end = sqrt(limit); i <= end; i++) {
			if (result[i]) {
				for (int j = i * i; j < result.Length; j += i)
					result[j] = false;
			}
		}
		return result;
	}
	
	
	// Given an integer limit, this returns a list of integers
	// where result[k] is the smallest prime factor of k.
	public static int[] SieveSmallestPrimeFactor(int limit) {
		if (limit < 0 || limit == int.MaxValue)
			throw new ArgumentOutOfRangeException("Limit out of range");
		int[] result = new int[limit + 1];
		if (limit > 0)
			result[1] = 1;
		for (int i = 2, end = sqrt(limit); i < result.Length; i++) {
			if (result[i] == 0) {
				result[i] = i;
				if (i <= end) {
					for (int j = i * i; j < result.Length; j += i) {
						if (result[j] == 0)
							result[j] = i;
					}
				}
			}
		}
		return result;
	}
	
	
	// Given an integer limit, this returns a list of integers
	// where result[k] is the totient (Euler phi function) of k.
	public static int[] SieveTotient(int limit) {
		if (limit < 0 || limit == int.MaxValue)
			throw new ArgumentOutOfRangeException("Limit out of range");
		int[] result = new int[limit + 1];
		for (int i = 0; i < result.Length; i++)
			result[i] = i;
		for (int i = 2; i < result.Length; i++) {
			if (result[i] == i) {
				for (int j = i; 0 <= j && j < result.Length; j += i)
					result[j] -= result[j] / i;
			}
		}
		return result;
	}
	
	
	// Given an integer limit, this returns a list of integers where result[k]
	// is the number of unique prime factors (omega function) of k.
	public static int[] SieveOmega(int limit) {
		if (limit < 0 || limit == int.MaxValue)
			throw new ArgumentOutOfRangeException("Limit out of range");
		int[] result = new int[limit + 1];
		for (int i = 2; i < result.Length; i++) {
			if (result[i] == 0) {
				for (int j = i; 0 <= j && j < result.Length; j += i)
					result[j]++;
			}
		}
		return result;
	}
	
	
	// Given an integer limit, this returns a list of integers where result[k]
	// is the product of the unique prime factors (radical function) of k.
	public static int[] SieveRadical(int limit) {
		if (limit < 0 || limit == int.MaxValue)
			throw new ArgumentOutOfRangeException("Limit out of range");
		int[] result = new int[limit + 1];
		for (int i = 1; i < result.Length; i++)
			result[i] = 1;
		for (int i = 2; i < result.Length; i++) {
			if (result[i] == 1) {
				for (int j = i; 0 <= j && j < result.Length; j += i)
					result[j] *= i;
			}
		}
		return result;
	}
	
	
	// Helper function: y = floor(sqrt(x)).
	private static int sqrt(int x) {
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	}
	
}