package arith;

import java.util.Arrays;
import java.util.BitSet;

// crible d'Ératosthène

public class Sieve {

  // crible
  static boolean[] sieve(int max) {
    boolean[] prime = new boolean[max + 1];
    for (int i = 2; i <= max; i++)
      prime[i] = true;
    for (int n = 2; n * n <= max; n++)
      if (prime[n])
        for (int m = n * n; m <= max; m += n)
          prime[m] = false;
    return prime;
  }

  // optim
  static boolean[] sieveOpt(int max) {
    boolean[] prime = new boolean[max + 1];
    prime[2] = true;
    for (int i = 3; i <= max; i += 2)
      prime[i] = true;
    for (int n = 3; n * n <= max; n += 2)
      if (prime[n])
        for (int m = n * n; m <= max; m += n)
          prime[m] = false;
    return prime;
  }

  static BitSet sieveBitSet(int max) {
    BitSet prime = new BitSet(max + 1);
    for (int i = 2; i <= max; i++)
      prime.set(i);
    for (int n = 2; n * n <= max; n++)
      if (prime.get(n))
        for (int m = n * n; m <= max; m += n)
          prime.clear(m);
    return prime;
  }
  
  static int[] firstPrimesUpto(int max) {
  	boolean[] prime = sieve(max);
  	int count = 0;
  	for (boolean b: prime) if (b) count++;
  	int[] res = new int[count];
  	for (int i = 2, next = 0; i <= max; i++)
  		if (prime[i])
  			res[next++] = i;
  	return res;
  }
  
  static int[] firstPrimesUptoOpt(int max) {
    boolean[] prime = new boolean[max + 1];
    for (int i = 2; i <= max; i++)
      prime[i] = true;
    int count = 0;
    for (int n = 2; n <= max; n++)
      if (prime[n]) {
        count++;
        for (int m = n * n; m <= max; m += n)
          prime[m] = false;
      }
    int[] res = new int[count];
    for (int i = 0, j = 0; i <= max; i++)
      if (prime[i]) res[j++] = i;
    return res;
  }

  static int[] firstNPrimes(int n) {
  	int m = Math.max(6, n);
  	int max = (int)(m * (Math.log(m) + Math.log(Math.log(m))));
  	boolean[] prime = sieve(max);
  	int[] res = new int[n];
  	for (int i = 2, next = 0; next < n; i++)
  		if (prime[i])
  			res[next++] = i;
  	return res;
  }

 public static void main(String[] args) {
   System.out.println(Math.sqrt(20));

   boolean prime[] = sieve(100);
    int count = 0;
    for (int i = 0; i < 100; i++)
      if (prime[i]) {
        System.out.print(i + ",");
        count++;
      }
    System.out.println();
    System.out.println(count + " primes");
    assert count == 25;

    BitSet primebs = sieveBitSet(100);
    count = 0;
    for (int i = 0; i < 100; i++)
      if (primebs.get(i)) {
        System.out.print(i + ",");
        count++;
      }
    System.out.println();
    System.out.println(count + " primes");
    assert count == 25;

    int[] primes = firstPrimesUpto(100);
    for (int p : primes)
      System.out.print(p + ",");
    System.out.println();
    System.out.println(primes.length + " primes");
    assert count == 25;

    int[] primes2 = firstNPrimes(25);
    assert Arrays.equals(primes, primes2);
    
    System.out.println("Sieve OK");
  }

}