carmichael

#include <iostream>
#include <cmath>

using namespace std;


// Struktura do przechowywania trojki liczb
typedef struct
{
    long d,x,y;
} value_t;



value_t extendedGCD (long a,long b)
{
  value_t w,tmp;

  if (b==0)
  {
      w.d=a;w.x=1;w.y=0;
      return w;
  }
  else
  {
      tmp=extendedGCD(b,a % b);
      w.d=tmp.d;
      w.x=tmp.y;
      w.y=tmp.x-(a/b)*tmp.y;
      return w;
  }
}

bool isPrime (long n)
{
    long double sqr=sqrt(n);

    for (long i=2;i<=sqr;i++)
    {
        if (n%i == 0)
            return false;
    }
    return true;
}


long powermod(long a,long b,long n)
{
    if (b==0)
        return 1;
    else
        if ((b % 2) == 0)
            return (powermod(a,b/2,n)*powermod(a,b/2,n)) % n;
        else
            return (a*powermod(a,(b-1)/2,n)*powermod(a,(b-1)/2,n)) %n;
}



bool isCarmichael(long N)
{
  //TODO
  for(int i = 2; i < N; i++){
      if(extendedGCD(N, i).d != 1) continue;
      if(powermod(i, N-1, N) != 1) return false;
  }
  return !isPrime(N);
}



int main()
{
    for (long N=2;N<=50000;N++)
    {
        if (!isPrime(N))
            if (isCarmichael(N))
                cout<<N<<endl;
    }
}