[인프런 - 파이썬 알고리즘 문제풀이] 2.7 소수(에라토스테네스 체)

인프런 > 파이썬 알고리즘 문제풀이

섹션 2.7 소수(에라토스테네스 체)

👊 내 문제 풀이

가장 원초적으로 풀어봤다. 숫자 i를 2 이상, i 미만의 수로 나눠 나머지가 0인 경우가 나오지 않을 경우, i는 소수라고 판단한다. 소수라고 판단하기 위해선 전체 경우의 수를 탐색해야 하기 때문에 시간 복잡도가 구린 코드다.

n=int(input())
sosu = [2]
is_sosu=False

for i in range(3,n):	#2는 소수, 3부터 소수 검사
	for j in range(2,i):
		if i%j==0:
			is_sosu=False
			break
		else:
			is_sosu=True
	if is_sosu == True:
		sosu.append(i)

print(len(sosu))

채점 결과

역시 시간 초과로 실패했다. 제목의 '에라토스테네스의 체'를 이용해서 다시 풀어보도록 하자.

 

 

에라토스테네스의 체는 합성수를 지워가며 소수를 찾는 알고리즘이다.

먼저 1은 제거하고, 순서대로 소수를 찾으며 그 소수의 배수는 모두 제거한다.

소수 2를 찾은 후 2의 배수는 모두 지우고, 다음 소수 3을 찾은 후 3의 배수를 모두 제거한다.

이 과정을 반복해가며 범위 내의 소수를 찾는다.

 

[출처] 에라토스테네스의 체

 

 

강의 해설 일부를 먼저 보고 참고해서 코드를 작성했다.

먼저 n+1 크기의 리스트를 True로 초기화해주고, 그 중 0과 1은 False로 제외시켰다.

2부터 n까지 반복문을 돌며 해당 인덱스가 True일 경우, 소수라고 판단하여 cnt에 +1을 해준다.

다음 그 소수의 배수들을 전부 찾아 False로 제외시킨다. 이 과정을 반복하면 마지막에는 소수만 남게 된다.

 

n=int(input())
numList=[True]*(n+1)
numList[0]=False    #0,1은 제외
numList[1]=False
cnt=0

for i in range(2, n+1):
    if numList[i] == True:    #True면 소수
        cnt+=1
        for j in range(i+i, n+1, i):  #소수 i의 배수들은 모두 제외(False)
            numList[j] = False;
print(cnt)

채점 결과

 

💡 강의 해답

n=int(input())
ch=[0]*(n+1)
cnt=0	
for i in range(2, n+1):
    if ch[i]==0:    
        cnt+=1
        for j in range(i, n+1, i):  
            ch[j]=1
print(cnt)

에라토스테네스의 체