3131. 100만 이하의 모든 소수 (코딩테스트, SW Expert Academy)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS 

SW Expert Academy

 

나의코드(1차)

N = 1000000
arr= [True]*(N+1)

for i in range(2,N+1):
    if arr[i]:
        for j in range(i*2,N+1,i):
            arr[j] = False
for i in range(2,len(arr)):
    if arr[i]:
        print(i,end = " ")

나의코드(2차)

N = 1000000
arr= [True]*(N+1)

for i in range(2,int(N**0.5)+1):
    if arr[i]:
        for j in range(i*2,N+1,i):
            arr[j] = False
for i in range(2,len(arr)):
    if arr[i]:
        print(i,end = " ")

 

기존에 알고있던 약수들을 구하는 코드로 2개를 가지는 것이 소수라고 판단하는 메소드를 통해서 소수를 출력하게 

만들었으나 전부 시간초과로 제출도 하지 못하였다.

결국 인터넷 검색을 통해 에라토스테네스의 체를 알게되었다.

 

해당 내용을 이해한 다음 다른사람 코드를 보지않고 내 방식대로 만들어보았다. (1차)

인덱스를 값으로 인식하고 해결하는 방법으로 해결하였는데 다른사람 코드를 리뷰하면서 비슷하다고 생각이 들었다.

 

추가적으로 1차에서 for i in range(2,N+1): 식으로 O(N)탐색을 진행했지만 제곱근만큼 돌려도 동일한 결과라고 한다.

 

2차에서 제곱근으로 변경해서 돌려도 결과는 같았다.

에라토스테네스의 체

2부터 시작해서 범위내의 숫자들 중에서 그의 배수가 되는 숫자들을 제외시킨다.

100만 이하 숫자를 예롤 들면

2 : 4 ,6, 8, 10 ..... 100만 제외 (제외시킬 기준이 되는 2라는 수는 살려둔다.(소수))

3 : 6, 9, 12, 15 .....제외 

이런식으로 제외시킨다. 배수가 되는 숫자는 소수가 될 수 없으니깐