초보자를 위한 Python 연습

Python으로 소수 판별하기

이 레슨에서는 제곱근까지만 약수를 확인해 어떤 수가 소수인지 판별합니다.

  • 초급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

소수는 인터넷 암호, 해시 테이블, 많은 퍼즐의 바탕에 있습니다. 그 수까지 모든 약수를 시도하며 소수인지 확인하는 방법은 29에는 통하지만, 큰 수에는 끔찍하게 느려집니다. 작은 통찰 하나로 확인이 훨씬 빨라집니다.

일상 속 비유

약수를 찾는 것은 타일로 빈틈없는 직사각형을 만들어 보는 것과 같습니다. 타일 36장은 1×36, 2×18, 3×12, 4×9, 6×6으로 놓을 수 있습니다. 정사각형(6×6)을 지나면 같은 직사각형이 방향만 바뀌어 다시 나오므로, 제곱근 너머에서는 새로 찾을 것이 없습니다. 타일 29장은 1×29로만 놓을 수 있으니 29는 소수입니다.

타일 직사각형에서 코드로
number > 1🚪 1보다 큰 수만 소수가 될 수 있습니다
divisor * divisor <= number🪞 정사각형에서 멈춥니다: 그 뒤는 반복입니다
number % divisor == 0🔍 빈틈없는 직사각형이 나옵니다: 소수가 아닙니다
divisor += 1➡️ 다음 너비를 시도합니다
제곱근까지 약수를 못 찾으면 그 수는 소수입니다.
한 문장으로

소수는 1보다 큰 정수 중 양의 약수가 1과 자기 자신뿐인 수입니다.

핵심 포인트

  1. is_prime = number > 1 은 절대 소수가 아닌 0, 1, 음수에 대해 False 로 시작합니다.
  2. while divisor * divisor <= number and is_prime: 은 제곱근에서, 또는 약수를 찾는 즉시 멈춥니다.
  3. number % divisor == 0 은 divisor 가 그 수를 정확히 나눈다는 뜻입니다.
  4. 29는 2, 3, 4, 5만 시도하면 소수라고 말할 수 있습니다.

언제 사용하나요?

  • 소수 나열이나 소인수 찾기 같은 숫자 퍼즐과 연습.
  • 일찍 멈추기와 한도까지만 확인하기가 왜 반복문을 빠르게 하는지 배우기.
  • 수학 도구에서 입력 검증하기.

필요 없는 경우

  • 큰 한도까지 모든 소수 나열하기: 에라토스테네스의 체가 수마다 확인하는 것보다 훨씬 빠릅니다.
  • 수백 자리 수를 쓰는 암호: 실제 시스템은 확률적 검사를 씁니다.

예제 코드

코드 실행 →
main.py
number = 29
is_prime = number > 1

divisor = 2
while divisor * divisor <= number and is_prime:
    if number % divisor == 0:
        is_prime = False
    divisor += 1

print(f"{number} is prime: {is_prime}")
이 예제의 실행 버튼 만들기

실행 결과

29 is prime: True

코드 설명

반복문은 divisor * divisor <= number인 동안만 약수를 확인하면 됩니다. n이 제곱근보다 큰 약수를 가진다면, 그 약수는 반드시 반복문이 이미 확인한 더 작은 약수와 짝을 이루기 때문입니다. 그래서 복잡도가 O(√n)으로 줄고, 결과는 29가 소수임을 보여 줍니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 입력 데이터를 바꾸고 실행하기 전에 결과를 예상해 보세요.
  2. 비어 있거나 잘못된 데이터를 확인하는 코드를 추가해 보세요.
  3. 처리 부분을 별도의 함수로 분리하고 여러 데이터로 테스트해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

1을 소수로 취급하기

1은 약수가 하나뿐이라 소수가 아닙니다. 먼저 number > 1 을 확인합니다.

문제
is_prime = True  # 1 would be reported as prime
수정
is_prime = number > 1

그 수까지 끝까지 돌기

답은 맞지만 필요한 것보다 훨씬 많은 약수를 시도합니다.

문제
for divisor in range(2, number):
수정
while divisor * divisor <= number:

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지