수학 - 최대공약수,소수

유클리드 호제법

• 최대공약수를 구하는 빠른 방법

  소수

• 약수가 1과 자기 자신 밖에 없는 수

• N이 소수가 될려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

  소수를 구하는 방법

  방법 1) 어떤 수 N이 소수인지 아닌지 판별하는 방법

• 2부터 N-1까지의 숫자로 나누어 떨어지는 확인 -> O(N)

  방법 2) N이하의 모든 소수