소수 판별 이론 (에라토스테네스의 체, 골드바흐의 추측)

소수 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. (1과 본인 외의 약수가 없는 수) 가장 작은 소수는 2로, 유일한 짝수이다. 에라토스테네스의 체 (자연수 n까지의 소수 구하는 방법) 1. n+1개 크기의 배열 생성 후 True로 초기화 2. 최소 소수인 2부터 sqrt(n)까지 확인하면서 2-1. 소수인 경우(True), 본인보다 큰 (본인을 제외) 본인의 배수를 모두 False로 바꿔줌 3. 배열에서 소수인 애들의 인덱스를 0과 1을 제외하고 리턴 sqrt(n)까지만 확인하는 이유 n까지 해도 값의 차이는 없다. 다만, n을 소수에서 제외시킬 수 있는 약수는 sqrt(n)이하일 수 밖에 없기때문에 불필요한 연산을 없애 시간을 줄여준다. 예) n = 10 / n의 약수..
이론공부 2020. 12. 9. 02:11
1