📒 문제 정보
- 관련 개념 : Loop
- 난이도 : level 1
- 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12921
🔑 문제 풀이
단순 반복문 풀이 - 시간초과
이중 for문을 활용하여 n보다 작은 수로 나누어지면 반복문을 break 하고, 그 어떠한 수로도 나누어지지 않으면 cnt+=1을 하여 소수의 개수를 찾는 방법이다.
def solution(n):
cnt = 0
for num in range(2, n+1):
for i in range(2, num):
if num % i == 0:
break
else:
cnt += 1
return cnt💡 Tip :
for...else구문for x in range(4): if x == 2: print('Loop out') break else: print('Loop end')위의 예시처럼, for문에서 루프 중간에
break로 빠져나오는 경우가 있는데 이때 for문과 같은 레벨에els를 두면break없이 빠져나온 경우만을 따로 처리할 수 있다.
에라토스테네스의 체 (Sieve of Eratosthenes)
n까지의 소수를 구한다고 하면,
- 2를 제외한 모든 2의 배수를 num에서 제거
- 3을 제외한 모든 3의 배수를 num에서 제거
- (4는 아까 윗 단계에서 제거됨)
- 5를 제외한 모든 5의 배수를 num에서 제거
- ...
이러한 방식으로 num에 남아있는 수들이 소수가 되는 방법이다.
def solution(n):
cnt = 0
for num in range(2, n+1):
for i in range(2, num):
if num % i == 0:
break
else:
cnt += 1
return cnt👉🏻 Tip
처음에는 i를 제외한 모든 i의 배수를 구하는 방법이
set(range(2*i, n+1, i))인 것이 처음에 잘 이해가 가지 않아 어려웠다.➡ 다음과 같이 이해하면 기억하기 쉽겠다.
▪start=2*i: i를 제외한 i의 첫 번째 배수
▪stop=n+1: n이 범위 중 마지막 수
▪step=i: i의 배수를 구하기 위함
💡 What I learned
-
for...else문 -
에라토스테네스의 체
