#include <iostream>
#include <vector>
#include <chrono>
#include <cassert>
#include <cmath>

using namespace std;

const int primeLimit = 10000000;

int powm(int base, int exp, int mod) {
  assert(exp > 0);
  int64_t y=1, x=base%mod;
  for (exp%=mod; exp>1; exp >>= 1) {
    if (exp&1)
      y = x*y %mod;
    x = x*x%mod;
  }
  return x*y%mod;
}
int gcd(int a, int b) {
  return !b ? a : gcd(b, a%b);
}

int main()
{
  cout << "Carmichael Numbers:" << endl << endl;

  ////////////////////////// Generate primes lookup table ///////////////////////////////////////////////////////////

  vector<int> prime_list;
  vector<bool> primes(primeLimit + 1, true); // calculated primes
  primes[0] = primes[1] = false;
  int iMax = (int)sqrt((double)primeLimit) + 1;
  for (int i = 2; i < iMax; ++i)
    if (primes[i]) {
      prime_list.push_back(i);
      for (int j = 2 * i; j < primeLimit + 1; j += i)
        primes[j] = false; // Erastothenes sieve
    }

  //////////////////////////  Fermat's little theorem ///////////////////////////////////////////////////////////////

  auto start_time = chrono::high_resolution_clock::now();

  for (int p = 2; p <= primeLimit; ++p) {
    if (primes[p])
      continue;
    bool ok=true;
    
    for (int a : prime_list) {
      if (a >= p)
        break;
      if (gcd(a,p)==1 && powm(a, p - 1, p) != 1) {
        ok=false;
        break;
      }
    }

    if (!ok)
      continue;
      
    auto end_time = chrono::high_resolution_clock::now();
    cout << p;
    cout << "\ttime: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << " ms" << endl;
  }
}