#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;
  }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNtYXRoPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBwcmltZUxpbWl0ID0gMTAwMDAwMDA7CgppbnQgcG93bShpbnQgYmFzZSwgaW50IGV4cCwgaW50IG1vZCkgewogIGFzc2VydChleHAgPiAwKTsKICBpbnQ2NF90IHk9MSwgeD1iYXNlJW1vZDsKICBmb3IgKGV4cCU9bW9kOyBleHA+MTsgZXhwID4+PSAxKSB7CiAgICBpZiAoZXhwJjEpCiAgICAgIHkgPSB4KnkgJW1vZDsKICAgIHggPSB4KnglbW9kOwogIH0KICByZXR1cm4geCp5JW1vZDsKfQppbnQgZ2NkKGludCBhLCBpbnQgYikgewogIHJldHVybiAhYiA/IGEgOiBnY2QoYiwgYSViKTsKfQoKaW50IG1haW4oKQp7CiAgY291dCA8PCAiQ2FybWljaGFlbCBOdW1iZXJzOiIgPDwgZW5kbCA8PCBlbmRsOwoKICAvLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLyBHZW5lcmF0ZSBwcmltZXMgbG9va3VwIHRhYmxlIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCgogIHZlY3RvcjxpbnQ+IHByaW1lX2xpc3Q7CiAgdmVjdG9yPGJvb2w+IHByaW1lcyhwcmltZUxpbWl0ICsgMSwgdHJ1ZSk7IC8vIGNhbGN1bGF0ZWQgcHJpbWVzCiAgcHJpbWVzWzBdID0gcHJpbWVzWzFdID0gZmFsc2U7CiAgaW50IGlNYXggPSAoaW50KXNxcnQoKGRvdWJsZSlwcmltZUxpbWl0KSArIDE7CiAgZm9yIChpbnQgaSA9IDI7IGkgPCBpTWF4OyArK2kpCiAgICBpZiAocHJpbWVzW2ldKSB7CiAgICAgIHByaW1lX2xpc3QucHVzaF9iYWNrKGkpOwogICAgICBmb3IgKGludCBqID0gMiAqIGk7IGogPCBwcmltZUxpbWl0ICsgMTsgaiArPSBpKQogICAgICAgIHByaW1lc1tqXSA9IGZhbHNlOyAvLyBFcmFzdG90aGVuZXMgc2lldmUKICAgIH0KCiAgLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8gIEZlcm1hdCdzIGxpdHRsZSB0aGVvcmVtIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKICBhdXRvIHN0YXJ0X3RpbWUgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CgogIGZvciAoaW50IHAgPSAyOyBwIDw9IHByaW1lTGltaXQ7ICsrcCkgewogICAgaWYgKHByaW1lc1twXSkKICAgICAgY29udGludWU7CiAgICBib29sIG9rPXRydWU7CiAgICAKICAgIGZvciAoaW50IGEgOiBwcmltZV9saXN0KSB7CiAgICAgIGlmIChhID49IHApCiAgICAgICAgYnJlYWs7CiAgICAgIGlmIChnY2QoYSxwKT09MSAmJiBwb3dtKGEsIHAgLSAxLCBwKSAhPSAxKSB7CiAgICAgICAgb2s9ZmFsc2U7CiAgICAgICAgYnJlYWs7CiAgICAgIH0KICAgIH0KCiAgICBpZiAoIW9rKQogICAgICBjb250aW51ZTsKICAgICAgCiAgICBhdXRvIGVuZF90aW1lID0gY2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwogICAgY291dCA8PCBwOwogICAgY291dCA8PCAiXHR0aW1lOiAiIDw8IGNocm9ubzo6ZHVyYXRpb25fY2FzdDxjaHJvbm86Om1pbGxpc2Vjb25kcz4oZW5kX3RpbWUgLSBzdGFydF90aW1lKS5jb3VudCgpIDw8ICIgbXMiIDw8IGVuZGw7CiAgfQp9