//
// IsPrime.cpp : Determines if an integer value is prime.
//
// g++ -Wall -O2 -std=c++14 -DNDEBUG IsPrime.cpp
//
#include <iostream>


int64_t power(int a, int n, int mod)
{
  int64_t power  = a;
  int64_t result = 1;

  while(n)
  {
   if (n & 1)
     result = (result * power) % mod;
   power = (power * power) % mod;
   n >>= 1;
  }

  return result;
}

bool witness(int a, int n)
{
  int t;
  int u;
  int i;
  int64_t prev;
  int64_t curr;

  u = n / 2;
  t = 1;

  while (!(u & 1))
  {
    u /= 2;
    ++t;
  }

  prev = power(a, u, n);
  for (i = 1; i <= t; ++i)
  {
    curr = (prev * prev) % n;
    if ((curr == 1) && (prev != 1) && (prev != n - 1))
      return true;
    prev = curr;
  }

  if (curr != 1)
    return true;
  return false;
}


inline bool IsPrime(int number)
{
  if (((!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3))
    return (false);

  if (number < 1373653)
  {
    for ( int k = 1; 36 * k * k - 12 * k < number; ++k)
      if ((number % (6 * k + 1) == 0) || (number % (6 * k - 1) == 0))
        return false;

    return true;
  }

  if (number < 9080191)
  {
    if (witness(31, number)) return false;
    if (witness(73, number)) return false;
    return true;
  }


  if (witness(2, number))  return false;
  if (witness(7, number))  return false;
  if (witness(61, number)) return false;
  return true;

  /*WARNING: Algorithm deterministic only for numbers < 4,759,123,141 (unsigned int's max is 4294967296)
    if n < 1,373,653, it is enough to test a = 2 and 3.
    if n < 9,080,191, it is enough to test a = 31 and 73.
    if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
    if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
    if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13.
    if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.*/
}


int main()
{
  for (int i = 0; i < 10000000; i++)
  {
    if (IsPrime(i))
      std::cout << i << std::endl;
  }

  return 0;
}