[Python-CodingTest] 2-7. 소수 (에라토스테네스의 체)

소수 (에라토스테네스의 체)

문제 정리

입력

20 // n

처리 과정

1. 리스트의 인덱스 번호를 n까지 생성 & 0으로 초기화
2. for문 돌면서 lst[i]가 0이면 cnt 1 증가
3. lst[]의 인덱스 중에 i의 배수들은 모두 1로 체크하기
4. 2~3번 반복

출력

8

풀이

import sys
sys.stdin = open("./input/in7.txt", "rt")

n = int(input())

# 인덱스 번호를 n까지 생성
lst = [0]*(n+1)
cnt=0

for i in range(2,n+1): # n까지 돌아야함
    if lst[i]==0:
        cnt+=1
        for j in range(i,n+1,i): # i부터 n까지 i의 배수로 돌기
            lst[j]=1 # 1을 대입해서 체크

print(cnt)

정리

• 에라토스테네스의 체 문제 풀때는 인덱스 번호와 수를 동일시
  예를들어 n=5라면 lst[1]~lst[5]까지 생성 (0번 인덱스는 버리는셈,, lst = [0]*6)
• range(2,10,3): 2부터 9까지 3씩 점프하면서 순회 (2,5,8)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기