[삼성 sw 파이썬] 3131. 100만 이하의 모든 소수

[삼성 sw 파이썬] 3131. 100만 이하의 모든 소수

문제

1 이상 100만 이하의 도든 소수를 구하는 프로그램을 작성하시오.

 

출력

1 이상 100만 이하의 소수를 공백을 사이에 두고 한 줄에 모두 출력한다.

 

풀이

1부터 100만 이하의 수를 하나하나씩 소수인지 판별하도록 코드를 작성하면 시간 초과가 나는 문제이다.

그렇기에 소수가 나오면 그 소수의 모든 배수를 배제하는 형식으로 코드를 작성하였다.

소수가 나올 경우 기록하기 위해서 100만까지 값이 0인 리스트를 만들었고

만약 이 리스트의 값이 0 이면 소수 임으로 이 값의 모든 배수를 1로 바꾸면서 제외하여 100만까지의 수를 판별하도록 만들었다.

코드

ans=[0]*1000001

for i in range(2,1000001):
    if ans[i]==0:
        for j in range(i,1000001,i):
            ans[j]=1
        print(i,end=" ")