$wonjjong

에라토스테네스의 체는 자연수에서 소수를 찾아내는 방법입니다. 소수란 약수가 1과 자기 자신뿐인 자연수를 말합니다. (1은 제외) 에라토스테네스의 체 알고리즘은 다음과 같습니다. 1) 1은 소수에서 제외되므로 2부터 소수인 수를 찾는다. 2) 2(P=2)가 소수이므로 2의 배수 2,4,6,8, ...를 전부 제외한다. 3) 다음 소수인 3(P=2)의 배수 3,6,9, ...를 전부 제외한다. 4) 다음 소수인 5(P=2)의 배수 5,10,15,20, ...를 전부 제외한다. 5) 이 방법을 계속해서 반복한다. (2부터 N까지의 숫자 중에서 에라토스테네스의 체로 소수를 찾을 때, P의 제곱이 N보다 커질 때까지 반복하면 된다.)

유클리드 알리고즘유클리드 알고리즘은 최대공약수를 효율적으로 구하는 알고리즘입니다. 최대공약수란?두 개 이상의 자연수가 주어졌을 때 공통된 약수중 가장 큰 약수를 최대 공약수라고 합니다. 예시 : 32와 24의 최대공약수 구하기32의 약수 = {1, 2, 3, 4 ,6, 8, 12, 24}24의 약수 = {1, 2, 4, 8, 16, 32} 32와 24의 공약수는 {1, 2, 4, 8}이고 이 중 가장 큰 약수인 8이 최대 공약수 입니다. 최대 공약수인 8의 약수는 {1, 2, 4, 8}입니다. 근데 이 약수들은 두 수의 공약수들과 같죠? 그러므로 최대공약수를 알면 최대 공약수를 통해 두 수의 공약수들 또한 알 수 있습니다. 유클리드 알고리즘이란?일반적으로 두 수 A, B가 주어졌을 때 A = B * q ..