정의를 먼저 알아보세요
소수는 정확히 두 개의 양의 약수(1과 숫자 자체)가 있는 1보다 큰 정수입니다. 첫 번째 소수는 2, 3, 5, 7, 11, 13입니다. 숫자 1은 소수도 합성수도 아니며, 2만이 유일한 짝수입니다.
제곱근까지만 확인
양의 정수 n을 테스트하기 위해 n 아래의 모든 숫자를 시도할 필요는 없습니다. n의 인수가 제곱근보다 큰 경우 제곱근보다 작은 일치 인수도 있어야 합니다. 따라서 가능한 제수를 제곱근까지 테스트하는 것으로 충분합니다.
- 2보다 작으면 소수가 아닙니다.
- 2로 나누어 떨어지는지 확인하세요. 짝수이고 2보다 크면 소수가 아닙니다.
- 3부터 제곱근까지 홀수 제수를 시도해 보세요. 균등하게 나누면 그 숫자는 합성수입니다.
- 균등하게 나누어지는 숫자가 없으면 그 숫자는 소수입니다.
예: 97은 소수인가요?
97의 제곱근은 10보다 약간 작습니다. 그 지점까지 가능한 소수 약수를 확인하세요: 2, 3, 5, 7. 숫자는 그 어떤 것으로도 나누어지지 않으므로 97이 소수입니다.
91의 경우 검사 결과 7: 91 ¼ 7 = 13이 발견되었습니다. 이는 91이 합성수라는 것을 보여주기에 충분합니다. 더 큰 제수를 테스트할 필요가 없습니다.
일반적인 실수
- 1 소수를 호출합니다. 소수에는 정확히 두 개의 양의 약수가 있어야 하지만 1에는 단 하나의 약수가 있어야 합니다.
- 모든 홀수가 소수라고 가정합니다. 9, 15, 21, 91과 같은 홀수 합성수에는 홀수 약수가 있습니다.
- 큰 숫자에 대해 몇 개의 작은 제수만 테스트합니다. 검사에서는 제곱근까지 가능한 모든 제수를 다루거나 검증된 소수 알고리즘을 사용해야 합니다.
UsefulVerse는 브라우저에서 로컬로 실제 정수 입력을 확인합니다. 주요 결과는 암호화 키에 대한 증명이나 특수 수론 소프트웨어의 대체품이 아닌 분할성 검사입니다.