sqrt(n)까지의 소수 판정
하나의 수를 효율적으로 검사합니다
sqrt(n)까지의 소수 판정은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
소수 판별 문제
핵심적인 수학 능력 중 하나는 하나의 수가 소수인지 판단하는 것입니다. 소수는 약수가 정확히 두 개, 즉 1과 자기 자신뿐입니다. 빠르게 테스트해 보겠습니다. 🔍
순진한 확인 방법
2부터 n-1까지의 모든 수로 n을 나누어 볼 수 있습니다. 정확하기는 하지만 n이 크면 매우 느립니다.
제곱근 요령
핵심 통찰은 n의 제곱근까지만 약수를 테스트하면 된다는 것입니다. 그보다 큰 곳에서는 새로운 인수가 나타날 수 없습니다.
제곱근으로 충분한 이유
약수는 곱해서 n이 되는 쌍으로 나타납니다. 두 수가 모두 제곱근보다 크다면 그 곱이 n을 초과하게 되므로 불가능합니다.
반복문의 경계
i*i가 n 이하인 동안 i를 2부터 증가시키며 반복합니다. i*i를 사용하면 큰 정수에서 sqrt로 인해 발생하는 부동 소수점 오차를 피할 수 있습니다.
while i * i <= n:
...작은 경우 처리하기
2보다 작은 수는 절대 소수가 아니므로 처음에 제외합니다. 이 검사를 두면 본문 반복문을 깔끔하고 올바르게 유지할 수 있습니다.
if n < 2:
return False전체 함수
이제 하나로 합쳐 보겠습니다. 작은 값을 먼저 검사한 다음 제곱근까지 가능한 약수를 살핍니다. 나누어떨어지는 수가 하나라도 있으면 n은 합성수입니다.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True더 빠르게 만들기
2는 따로 확인하고 홀수만 테스트하십시오. 짝수를 건너뛰면 복잡도를 추가하지 않고 작업량을 대략 절반으로 줄일 수 있습니다.
if n % 2 == 0:
return n == 2시간 비용
이 테스트는 O(sqrt n) 시간에 실행됩니다. 10억 이하의 수 하나라면 저렴한 연산을 약 30,000번만 수행하면 됩니다.
하나의 수, 여러 수가 아님
제곱근 테스트는 하나 또는 몇 개의 질의에서 효과적입니다. 전체 범위에 대해 소수 여부를 확인해야 한다면 체가 훨씬 빠릅니다.
제곱근의 함정 피하기
math.sqrt 대신 i*i와 비교하면 경계에 있는 수를 잘못 받아들이거나 거부하게 만드는 반올림 오차를 피할 수 있습니다.
빠른 확인
이 테스트를 빠르게 만드는 경계를 확인하십시오.
복습
이제 하나의 수가 소수인지 O(sqrt n) 시간에 테스트하고, 작은 값을 먼저 검사하며, 짝수를 건너뛰고, 정확성을 유지하기 위해 i*i를 사용할 수 있습니다. ✅
자주 묻는 질문
“sqrt(n)까지의 소수 판정” 강의는 무료인가요?
네 — “sqrt(n)까지의 소수 판정” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“sqrt(n)까지의 소수 판정”에서 뭘 배우나요?
하나의 수를 효율적으로 검사합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“sqrt(n)까지의 소수 판정” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- GCD, LCM과 유클리드 알고리즘
- sqrt(n)까지의 소수 판정
- 에라토스테네스의 체
- 소인수 분해와 약수