백준(baekjoon) 1929번: 소수 구하기(실버 3, 파이썬 PYTHON) - 기본 수학2

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

import sys

M,N=map(int,sys.stdin.readline().split())
check_prime=[True]*(N+1)
check_prime[1]=False  

for x in range(2,N+1): 
  for y in range(2*x,N+1,x):
    if(check_prime[y]==True):
      check_prime[y]=False 

for x in range(M,N+1):
  if(check_prime[x]==True): 
    print(x)

 

※ 기본 수학 2

 

 

● True로 초기화 된 길이가 N+1인 배열 check_prime을 만들어준다.(현재 확인하는 값을 인덱스와 그대로 비교하기 위해 N+1의 길이 배열 사용.)

 

● 1은 소수가 아니므로 check_prime[1]의 값은 미리 False로 바꿔준다.

 

● 2부터 N까지 순회하고, 이 숫자의 배수는 무조건 소수가 아님을 이용하여 이 숫자의 배수를 갖는 인덱스의 요소를 False로 바꾸어준다.

 

● 마지막에 배열을 돌며 요소가 True인 인덱스를 출력해주면 해결!!

 

 

결과

 

 

♣ 참고: 에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전