수학

유클리드 호제법(최대공약수)

GCD(A, B)=GCD(B, A% B)이다.

계속하다가 A%B가 0이 될 때 B가 원래 A, B의 최대 공약수가 된다.

EX) (6,4)->(4,2)->(2,0) 6,4의 최대 공약수는 2

최소공배수는 A*B/GCD(A, B)이다.

 

소수 구하기

제일 좋은 방법은 에라토스테네스의 체이다.

시간 복잡도는 N개의 수에 대한 소수를 구할 때 NlglgN이다.

 

2에서부터 N까지 수에서 제일 작은 수로 나누어지는 수를 삭제한다.

그럼 처음에는 4, 6, 8... 이 없어진다.

다음에는 제일 작은 수인 3으로 나누어지는 수를 삭제한다.

 

삭제되는 것을 잘 보다 보면 2를 삭제할 때는 삭제되는 처음 수가 2*2이고 3을 삭제할 때는 삭제되는 처음 수가 3*3인 것처럼 처음 삭제되는 수는 i*i인 것을 알 수 있다. 

이것을 적용하여 처음부터 i*i의 수부터 삭제한다.

 

마지막으로 남은 숫자들을 출력하면 해당 범위의 소수를 구할 수 있게 된다.