소수찾기
[Prime Number] 유클리드 호제법 (소수 찾기)
최대 공약수를 구하는 방법 중의 하나이다. 호제법은 두수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 개요 1071과 1029의 최대공약수를 구하면, 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42..
[Prime Number] 에라토스테네스의 체 (소수 찾기)
소수 판별법의 일종으로, 2부터 N까지의 자연수를 나열하고 2의 배수, 3의 배수, N//2 의 배수를 찾아가며 지워간다. 이후 남는 숫자가 2~N사이의 소수이다. APS에 심심치 않게 볼수 있는 소수를 찾는 방법 중하나이다. 중~하 문제에서 많이 나오기때문에 꼭 숙지하는 것이 좋다.소수는 약수가 1과 자기자신만 가지고 있는 숫자를 말한다. 소수를 찾는 방법은 직접 약수를 찾아가면서 소수인지 아닌지 확인하는 방법이 있다. 하지만 숫자에 범위에 따라 상황에 맞는 방법을 선택하면 실행속도가 더 빠르기 때문에 이 방법도 알아두는 것이 좋다. 개요 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기..