정수론

최대공약수

유클리드 호제법

최대공약수를 구하는 알고리즘

gcd(a,b) = gcd(b,a%b)

반복하다가 마지막에 나눠서 0으로 떨어지면 나눈 값이 최대공약수이다.

최소공배수: (a * b)/gcd(a,b)

static void euclid(int a, int b) {
    if(a%b == 0)
    	GCD = b;
    else
    	Euclid(b, (a%b));
}

소수 판별

N이하의 모든 수로 나누어 보는 것은 비효율적이므로 2~sqrt(N) 까지 나누어본다.

에라토스테네스의 체

소수의 배수들을 지워줌

for(int i=2; i*i<=N; i++) {
   for(int j=i*i; j<=N; j+=i) {
      isPrime[j] = false;
   }
}