“소수 출력/세기” 정리
소수(prime number) 문제는 코딩테스트에서 가장 기본이면서도 자주 나오는 유형이다. 단순 반복문과 조건문만으로도 풀 수 있고, 조금만 개선하면 훨씬 효율적으로 만들 수 있다.
1) 왜 자주 나오나
- 정수론(약수, 배수, 최대공약수·최소공배수 등)의 기초를 코드로 옮기는 연습이 되기 때문이다.
- 반복문, 조건문, break/continue 같은 제어 흐름을 정확히 쓰는지 확인하기 좋다.
- 처음엔 단순 구현으로 시작하고, 이후 점진적으로 효율 개선(시간 단축) 아이디어를 적용하는 연습을 하게 된다.
2) 소수의 정의와 기본 아이디어
- 소수 : 1과 자기 자신으로만 나누어떨어지는 2 이상의 자연수이다. (1은 소수가 아니다.)
- 어떤 수 i가 소수인지 확인하려면, 2부터 i-1까지 나누어 떨어지는 수가 있는지 검사하면 된다.
- 이 검사를 1부터 n까지 반복하면, 1~n 사이의 모든 소수를 구할 수 있다.
더보기
+ 수업 코드 설명
n = 100
# 할 일 : 1부터 n까지 소수들을 다 출력하세요!!!!
for i in range(2, n+1): # 2~n까지의 소수 테스트할 숫자들 라인업!!!
# 1개 i 숫자가 선태이 되었다고 하면,,,,
# ==> i숫자가 소수인지 아닌지 판별 룰: 2부터~i-1, i까지 살아오는지,,,,
for j in range(2, i+1): #i가 처음으로 나누어지는 j를 찾는 것이 목표
if i % j ==0:
break
if j ==i: #i가 처음으로 나누어지는 j가 i==j가 라면 소수가 맞으므로
print(i)
1) n = 100
- 소수를 구할 상한값을 100으로 둔다.
2) for i in range(2, n+1):
- i를 2부터 n까지(여기서는 100까지) 하나씩 증가시키며 검사한다.
- range(2, n+1)은 2, 3, …, 100을 생성한다.
- 각 i가 소수인지 판정하는 것이 목표다.
3) for j in range(2, i+1):
- i가 소수인지 확인하기 위한 나눗셈 시도 루프다.
- j를 2부터 i까지 검사한다. 여기서 핵심은 “i까지 포함”한다는 점이다.
- 파이썬 range는 상한 미포함이므로 range(2, i+1)을 써야 j가 i까지 도달한다.
- 이 루프의 의도는 “i가 처음으로 나누어떨어지는 j”를 찾는 것이다.
- 합성수라면 j가 i보다 작은 약수에서 먼저 걸리고,
- 소수라면 “나누어떨어지는 최초의 j”가 i 자체가 된다.
4) if i % j == 0:
- i를 j로 나눈 나머지가 0이면, 즉 나누어떨어지면 약수를 찾은 것이다.
- 이 순간 i가 합성수인지(혹은 마지막 순간 i로 나눴는지)를 판단할 수 있는 지점이다.
5) break
- 위 조건이 참이면 즉시 내부 for 루프를 종료한다.
- 즉, “처음으로 i를 나누어떨어지게 만든 j”에서 멈춘다.
- 합성수라면 그 j는 i보다 작은 약수다(예: i=6이면 j=2에서 멈춘다).
- 소수라면 j가 쭉 증가해서 마지막에 i에 도달했을 때 i % i == 0으로 멈춘다.
중요: break는 안쪽 for 루프만 깬다. 바깥의 for i ...는 계속 진행된다.
6) if j == i:
- 내부 루프가 끝난 뒤, 바깥에서 j의 값을 확인한다.
- 파이썬에서는 for 루프가 끝난 후에도 마지막에 사용된 루프 변수(j)를 참조할 수 있다.
- 이 코드의 논리는 다음과 같다.
- 합성수: i는 j가 i보다 작은 어떤 값에서 이미 나누어떨어져 break로 나왔다. 따라서 j != i다.
- 소수: i는 오직 자기 자신에서만 나누어떨어진다. 내부 루프는 j가 i에 도달한 순간 i % i == 0으로 break된다. 따라서 j == i다.
- 결과적으로 j == i이면 i가 소수라는 뜻이 된다.
주의 1: 이 코드는 i >= 2일 때만 안전하다. 만약 i가 1이면 range(2, i+1)이 비어 루프가 한 번도 돌지 않아 j가 정의되지 않은 채 if j == i:를 만나 에러가 난다. 하지만 이 코드에서는 i가 2부터 시작하므로 괜찮다.
주의 2: 이 방식은 “루프 끝난 뒤의 j 값”에 의미를 부여하는 트릭이므로 초보자에겐 가독성이 떨어질 수 있다. 일반적으로는 is_prime 플래그나 for-else를 권장한다.
7) print(i)
- 위 조건이 참일 때(즉 j == i일 때) i를 소수로 판정하고 출력한다.
동작 예시로 이해해보기
예시 1) i = 6 (합성수)
- j=2 → 6 % 2 == 0이므로 break
- 루프 종료 시 j는 2다(즉, j != i)
- if j == i:는 거짓이므로 출력하지 않는다.
예시 2) i = 7 (소수)
- j=2 → 7 % 2 != 0 계속
- j=3 → 7 % 3 != 0 계속
- …
- j=7 → 7 % 7 == 0이므로 break
- 루프 종료 시 j는 7이다(즉, j == i)
- if j == i:가 참이므로 7을 출력한다.
3) 가장 직관적인 풀이(기본형)
핵심 흐름은 다음과 같다.
- 후보 수 i를 2부터 n까지 순회한다.
- i가 소수인지 확인한다: 2부터 i-1까지 나누어보며, 하나라도 나누어떨어지면 합성수다.
- 끝까지 안 나누어지면 소수다 → 출력/카운트한다.
# 1~n 사이의 소수를 모두 출력하고 개수도 센다 (기본형)
n = 100
count = 0 # 소수 개수
for i in range(2, n + 1): # 후보 수 i: 2 ~ n
is_prime = True # 일단 소수라고 가정
for j in range(2, i): # 2 ~ i-1 까지 나눠보기
if i % j == 0: # 나누어떨어지면 합성수
is_prime = False
break # 더 볼 필요 없으니 중단
if is_prime:
print(i, end=" ")
count += 1
print("\\n소수 개수:", count)
- 위 코드로 n=100이면 2 3 5 7 11 ... 97이 출력되고, 개수는 25개가 된다.
- 가독성을 위해 is_prime 플래그를 쓰는 방식이 초보자에게 가장 이해하기 쉽다.
참고: 질문에 있는 코드처럼 for j in range(2, i+1) 뒤에 if j == i: print(i)로 판단하는 방식도 동작한다. 다만 루프 밖에서 j 값으로 판정하는 구조는 초보자에겐 다소 헷갈릴 수 있어, 위처럼 is_prime을 권장한다.
4) 제어문 맛보기: break, continue, pass
- break: 현재 반복을 즉시 종료한다. 위 코드에서 합성수임이 확인되면 더 나눠볼 필요가 없으니 쓴다.
- continue: 아래 코드를 건너뛰고 다음 반복으로 넘어간다.
- pass: 자리만 채우는 빈 문장이다. 나중에 코드를 채울 곳에 임시로 둔다.
for i in range(1, 6):
if i == 3:
continue # 3은 건너뛴다
if i == 5:
break # 5에서 반복 종료
# pass # 할 일 없을 때 형식만 유지하고 싶다면 사용
print(i)
# 출력: 1 2 4
5) 간단한 효율 개선: √i까지만 확인하기
- 수학적으로 어떤 수 i가 합성수라면, 반드시 √i 이하의 약수를 가진다
더보기따라서 i가 소수인지 확인할 때 2 ~ √i까지만 나눠보면 된다.반드시 √i 이하의 약수를 가진다.
1) 먼저, 약수는 짝을 이룬다
어떤 수 i가 있다면, i = a × b처럼 두 수의 곱으로 나타낼 수 있을 때가 있다.
이때 (a, b)는 **약수의 짝(pair)**이다.
- 예: 20 = 1×20 = 2×10 = 4×5
- 약수 짝은 (1,20), (2,10), (4,5)이다.
- 예: 36 = 1×36 = 2×18 = 3×12 = 4×9 = 6×6
핵심은 항상 짝으로 나타난다는 점이다. 하나가 작으면 다른 하나는 크다.
2) 만약 둘 다 √i보다 크다면 모순이 난다
√i는 “자기 자신을 곱하면 i가 되는 수”이다.
이제 생각 실험을 해보자.
- 만약 a > √i이고 b > √i라면?그런데 우리는 a×b = i여야 한다. 모순이다.
- 곱하면 a×b > √i × √i = i가 되어버린다.
따라서 i = a×b가 되려면, 적어도 하나는 √i보다 작거나 같아야 한다.
즉, 합성수 i에는 반드시 √i 이하인 약수가 하나 이상 존재한다.
3) 왜 검사 범위를 √i까지만 보면 충분한가
어떤 수 i가 합성수라면, 위에서 본 대로 약수의 짝 (a, b) 중 하나는 꼭 √i 이하다.
그러면 나눗셈 검사(2, 3, 4, …)를 할 때 √i까지만 검사하면 다음이 보장된다.
- √i 이하에서 나누어떨어지는 수가 한 번이라도 나오면 합성수다.
- √i 이하에서 단 한 번도 안 나누어떨어지면, 그보다 큰 수에서 처음으로 약수가 나올 가능성은 없다.
- 왜냐하면 큰 약수가 있다면 그 짝인 작은 약수가 √i 이하에 이미 있었어야 하기 때문이다.
그래서 소수 판정은 2부터 ⌊√i⌋까지만 보면 된다.
4) 직관 비유: 직사각형 넓이
i라는 넓이를 가진 직사각형을 생각한다. 가로를 a, 세로를 b라고 하자.
a×b = i를 만들려면, 가로나 세로 중 하나는 반지름 같은 기준 길이인 √i보다 작거나 같아야 한다.
둘 다 √i보다 크면 넓이가 i를 넘어버린다.
이 비유가 “약수 하나는 반드시 √i 이하”라는 사실과 1:1로 대응한다.
5) 예시로 확인하기
- i = 20, √20 ≈ 4.47왼쪽 수들을 보면 1, 2, 4가 모두 √20 이하다. 실제로 작은 약수가 존재한다.
- 약수 짝: (1,20), (2,10), (4,5)
- i = 49, √49 = 7그러니 2~7까지만 보면 충분하다.
- 약수 짝: (7,7) 하나뿐이다. 작은 약수(=7)가 딱 √i와 같다.
- i = 37, √37 ≈ 6.08그러면 7 이상에서 처음 약수가 나올 수 없다(나오려면 6 이하에 짝이 있었어야 하니까).
- 그래서 37은 소수다.
- 2~6까지 모두 나눠봐도 안 나눠떨어진다.
6) 한 줄 요약
- 합성수 i는 반드시 √i 이하의 약수를 가진다.
- 이유: 약수는 짝을 이루고, 둘 다 √i보다 크면 곱이 i를 초과하는 모순이 생긴다.
- 결론: 소수 판정은 2부터 ⌊√i⌋까지만 나눠보면 충분하다
# √i까지만 검사하는 개선 버전 import math n = 100 count = 0 for i in range(2, n + 1): is_prime = True # 2 ~ floor(√i)까지만 검사 for j in range(2, int(math.isqrt(i)) + 1): if i % j == 0: is_prime = False break if is_prime: print(i, end=" ") count += 1 print("\n소수 개수:", count)- 이 방법은 기본형보다 불필요한 나눗셈을 크게 줄여 훨씬 빠르다.
- 대략적인 시간복잡도는 O(n√n) 수준이다(기본형 O(n²)보다 개선).
6) 더 빠르게: 에라토스테네스의 체
많은 수의 소수를 한 번에 구할 때는 에라토스테네스의 체가 가장 유명하다.
아이디어
- 2부터 n까지를 모두 소수라고 가정한다.
- 2부터 시작해, 아직 소수로 표시된 수의 배수들을 지워나간다(합성수 표시).
- 지우기 시작하는 배수는 **자기 자신의 제곱(i*i)**부터 시작해도 충분하다(그보다 작은 배수는 이미 지워져 있음).
- 끝나면 소수로 남아 있는 수들이 결과다.
# 에라토스테네스의 체
n = 100
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 2 ~ √n 까지의 수로 배수를 지운다
import math
for i in range(2, int(math.isqrt(n)) + 1):
if is_prime[i]:
# i*i부터 n까지 i의 배수를 합성수로 표시
for j in range(i * i, n, i):
is_prime[j] = False
# 결과 출력 및 개수 세기
primes = [i for i in range(2, n + 1) if is_prime[i]]
print(*primes)
print("소수 개수:", len(primes))
- 체 알고리즘의 시간복잡도는 대략 **O(n log log n)**로 아주 빠르다.
- n이 커질수록 체의 효율이 크게 빛난다.
- 코드 상세 설명
더보기
코드 상세 설명
1) n = 100
- 소수를 구할 최댓값을 100으로 정한다. 이제 2부터 100까지 범위에서 소수를 찾는 문제로 고정된다.
2) is_prime = [True] * (n + 1)
- 길이가 n+1인 리스트를 만든다. 인덱스 = 실제 수가 되도록 맞추기 위해서다.
- 인덱스 0 → 수 0, 인덱스 1 → 수 1, …, 인덱스 100 → 수 100에 대응한다.
- 처음에는 전부 True로 채워 일단 다 소수라고 가정해 둔다. 이후에 합성수(소수가 아님)를 False로 지워 나간다.
3) is_prime[0] = is_prime[1] = False
- 0과 1은 소수가 아니므로 미리 False로 표시한다.
- 이렇게 하면 이후 출력·집계에서 0, 1이 소수처럼 섞이지 않는다.
4) import math
- 수학 유틸을 쓰기 위해 임포트한다. 여기서는 정수 제곱근을 구하는 math.isqrt를 사용한다.
5) for i in range(2, int(math.isqrt(n)) + 1):
- 바깥 루프다. **지울 기준이 되는 수 i*를 2부터 ⌊√n⌋까지 순회한다.
- 왜 √n까지만 보나? 합성수의 약수는 반드시 하나는 √i 이하이므로, i가 √n을 넘으면 새로운 배수를 지울 게 더 이상 생기지 않는다.
- math.isqrt(n)은 int(sqrt(n))와 같지만 부동소수 오차 없이 안전하게 바닥값을 준다.
- +1을 붙이는 이유는 파이썬의 range가 끝값 미포함이라서, 예를 들어 n=100이면 i=10까지 포함시키기 위해서다.
6) if is_prime[i]:
- i가 아직 소수로 남아 있는 경우에만 그 배수들을 지운다.
- 이미 이전 작은 소수의 배수로 지워진 합성수 i라면 다시 배수를 돌 필요가 없다(중복 작업 방지로 효율↑).
7) for j in range(i * i, n + 1, i):
- 안쪽 루프다. i의 배수들을 지우는 구간이다.
- 왜 시작을 i*i에서 하나?
- i * 2, i * 3, … 같은 더 작은 배수들은 이미 더 작은 소수들의 배수 지우기 단계에서 지워졌다.
- 예를 들어 기준이 5일 때, 5*2=10, 5*3=15, 5*4=20은 2나 3 단계에서 이미 지워졌다. 새롭게 의미 있는 시작점은 5*5=25부터다.
- 왜 n+1을 끝으로 쓰나?
- range(start, stop, step)에서 stop은 포함되지 않는다.
- n까지 포함해 지우려면 stop을 n+1로 지정해야 한다.
- 만약 n을 쓰면 … , n-2, n-1까지만 돌고 n이 배수여도 안 지워질 수 있다.
8) is_prime[j] = False
- j가 i의 배수이므로 합성수다. 소수가 아님을 표시하기 위해 False로 바꾼다.
- 이 과정을 모든 기준 i에 대해 반복하면, 합성수는 전부 False로 걸러지고, True만 소수로 남는다.
9) primes = [i for i in range(2, n + 1) if is_prime[i]]
- 리스트 컴프리헨션으로 결과 소수 목록을 만든다.
- 2부터 n까지 훑으면서 is_prime[i]가 True인 값들만 뽑아 새 리스트에 담는다.
- 여기서도 n을 포함하려고 range(2, n+1)을 쓴다.
10) print(*primes)
- 언패킹(*)을 써서 primes의 원소를 공백 구분으로 한 줄에 출력한다.
- 예를 들어 print(*[2,3,5])는 print(2, 3, 5)와 같다.
11) print("소수 개수:", len(primes))
- 소수의 개수를 출력한다. len(primes)가 1~n 사이 소수의 총 개수다.
덧붙임: 실제로 어떻게 지워지는지(아주 짧게)
- 처음엔 2~100을 전부 소수(True)라 가정한다.
- i=2일 때 4,6,8,…,100을 False로 만든다.
- i=3일 때 9,12,15,…,99를 False로 만든다(이미 False인 것도 다시 False일 뿐이라 문제 없다).
- i=5일 때 25부터 25,30,35,…,100을 지운다.
- i=7일 때 49부터 49,56,63,…,98을 지운다.
- i=11은 √100=10을 넘으므로 바깥 루프는 거기서 멈춘다.
- 남은 True 인덱스들이 곧 소수다.
요약
- is_prime을 True로 초기화 → 배수 지우기로 합성수만 False 처리 → 남은 True가 소수다.
- 바깥은 2~√n, 안쪽은 i*i~n(간격 i)로 도는 것이 핵심 아이디어다.
- range의 끝값 미포함을 잊지 말고, 배수 지우기 구간은 **n+1*로 잡아야 한다.
7) 자주 하는 실수 체크리스트
- 1은 소수가 아니다. 2부터 시작해야 한다.
- 범위를 잘못 잡지 말자: range(2, i)는 2~i-1이다.
- 루프 밖 변수로 판정하는 방식은 헷갈리기 쉬우니 **플래그(is_prime)**를 추천한다.
- 음수·0·1 처리 조건을 분명히 하자(보통 입력이 2 미만이면 소수 없음).
8) 확장 연습
- 1~n 사이 소수의 합을 구하라.
- k번째 소수를 구하라.
- 두 수의 최대공약수(GCD), **최소공배수(LCM)**를 함수로 만들어보라.
- 입력이 커질 때는 반드시 √i 검사 또는 에라토스테네스의 체를 적용하라.
9) 마무리
- 처음에는 단순 이중 반복으로 정확성을 확보한다.
- 다음으로 √i까지만 검사하는 방식으로 효율을 높인다.
- 마지막으로 많은 범위의 소수가 필요하면 에라토스테네스의 체를 사용한다.
- 이 과정에서 자연스럽게 반복문, 조건문, break/continue 같은 제어문 사용이 손에 익는다.
- 위 흐름만 정확히 이해하면, 소수 출력·개수 세기 문제는 충분히 안정적으로 풀 수 있다.
참고) i까지 나눠야하는 거 아닌가?
아니다. i까지 나눌 필요가 없다.
이유는 간단하다:
i로 나누면 i % i == 0이 항상 참이라서, “마지막에 가서야 처음으로 나누어떨어졌다”는 신호로만 쓰일 뿐이다. 그래서 range(2, i+1)를 쓰고 j == i인지로 판정하는 코드는 동작은 하지만 가독성이 떨어지는 트릭에 가깝다. 보통은 다음 둘 중 하나로 쓰는 게 명확하다.
1) 기본형: i-1까지만 검사
python
복사편집
for i in range(2, n + 1):
is_prime = True
for j in range(2, i): # 2 ~ i-1
if i % j == 0:
is_prime = False
break
if is_prime:
print(i)
2) 효율 개선: √i까지만 검사
python
복사편집
import math
for i in range(2, n + 1):
is_prime = True
for j in range(2, int(math.isqrt(i)) + 1): # 2 ~ ⌊√i⌋
if i % j == 0:
is_prime = False
break
if is_prime:
print(i)
파이썬스럽게 쓰고 싶다면 for-else도 좋다(가독성 ↑):
python
복사편집
for i in range(2, n + 1):
for j in range(2, int(math.isqrt(i)) + 1):
if i % j == 0:
break
else:
print(i) # break 한 번도 안 났을 때만 실행
정리하면, 정확성만 보면 i-1까지만 보면 충분하고, 속도까지 신경 쓰면 √i까지만 보면 된다.
'파이썬 > exercise' 카테고리의 다른 글
| [파이썬] exercise 05 반복문 패턴 (0) | 2025.08.09 |
|---|---|
| [파이썬] exercise 04 사각형 외내부 판정 (0) | 2025.08.05 |
| [파이썬] exercise 03 리스트 필터링 (1) | 2025.08.05 |
| [파이썬] exercise 02 리스트 변경 (0) | 2025.08.05 |
| [파이썬] exercise 01 과목 평균 (2) | 2025.08.05 |
