소수판별법1 에라토스테네스의 체, 소수판별법 에라토스테네스의 체 소수를 걸러내는 방법, 소수의 배수(합성수)들을 하나씩 지워나가 남는 것들은 소수라는 결론에 도달하는 방식이다 소수 판별법 소수는 1 과 자기 자신으로만 나누어 떨어지므로, n 이하의 모든 자연수를 대입하여 1외에 수로 나누어 떨어지는지 확인하면 되지만 모두 계산할 필요없이 n의 제곱근 이하의 값이 1외의 수로 나누어 떨어지는지 확인하면 된다 왜냐하면 n 이 소수가 아닌 합성수라면, n = a * b 로 나타낼 수 있는데(a,b는 1외의 자연수) a와 b는 모두 n의 제곱근 이하의 값을 가지므로, n의 제곱근에서 나누어지는 수(a와 b) 가 있는지만 확인하면 소수인지 아닌지를 구분 가능한것이다. 제곱근 n이하에서 나누어 떨어지면 합성수, 나누어 떨어지지 않으면 그 수는 소수이다 2022. 6. 10. 이전 1 다음