content: package by.andd3dfx.numeric;
  
  import java.util.Arrays;
  import java.util.BitSet;
  
  /**
   * Find amount of prime numbers which less than definite number N.
   * <p>
   * See <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
   *
   * @see <a href="https://youtu.be/VWP8mvmDRNc">Video solution</a>
   */
  public class AmountOfPrimeNumbers {
  
      public static int determine_usingPrimeDividersOfNumberSolution(int n) {
          int result = 0;
          for (int i = 2; i < n; i++) {
              if (isPrime(i)) {
                  result++;
              }
          }
          return result;
      }
  
      private static boolean isPrime(int number) {
          return PrimeDividersOfNumber.determine(number).length == 1;
      }
  
      public static int determine_usingCustomIsPrimeWithEarlyReturn(int n) {
          int result = 0;
          for (int i = 2; i < n; i++) {
              if (isPrimeEnhanced(i)) {
                  result++;
              }
          }
          return result;
      }
  
      private static boolean isPrimeEnhanced(int number) {
          for (int i = 2; i <= Math.sqrt(number); i++) {
              if (number % i == 0) {
                  return false;
              }
          }
          return true;
      }
  
      public static int determine_usingEratosthenesSieve(int n) {
          var isPrime = new boolean[n];
          Arrays.fill(isPrime, 2, n, true);
  
          for (var i = 2; i < n; i++) {
              if (isPrime[i]) {
                  for (var j = 2; j * i < n; j++) {
                      isPrime[i * j] = false;
                  }
              }
          }
  
          int result = 0;
          for (var item : isPrime) {
              if (item) {
                  result++;
              }
          }
          return result;
      }
  
      public static int determine_usingEratosthenesSieveWithBitSet(int n) {
          var isPrime = new BitSet(n);
          isPrime.set(2, n);
  
          for (var i = 2; i < n; i++) {
              if (isPrime.get(i)) {
                  for (var j = 2; j * i < n; j++) {
                      isPrime.clear(i * j);
                  }
              }
          }
  
          return isPrime.cardinality();
      }
  }
  