정수론 수학에서 정수론은 수의 성질을 공부하는 분야입니다. 실제 코딩테스트에서는 정수론의 분야가 굉장히 방대하기 때문에 가장 많이 등장하는 소수, 오일러 피, 호제법에 관련하여 학습합니다. 소수 소수(prime number) 는 자신보다 작은 2개의 자연수를 곱해서 만들 수 없는 1보다 큰 자연수를 말합니다. 1과 자기 자신 외에 약수가 없는 수입니다. 소수를 구하는 대표적인 방법은 에라토스테네스의 체가 있습니다. 에라토스테네스의 체 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성. 2. 2부터 시작해서 현재 숫자가 지워지지 않았다면 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 처음으로 선택된 숫자는 지우지 않습니다. 3. 배열의 끝까지 2를 반복한 후에 배열에서 ..
