5. 소수 구하기(에라토스테네스 체)

소수 구하기 (에라토스 테네스 체)

 

에라토스 테네스 체 : 걸러낸다는 뜻

 

n까지의 숫자가 있는 리스트

 

다음과 같이 CH 라는 리스트에 n까지의 숫자가 들어있다고 가정할 때, 소수만 카운트 하고 싶다면,

1을 제외하고 2부터 for문을 돌린다음 i의 배수가 되는 부분들을 지워나가면서 0으로 남은 부분만 카운트 하면 된다!

 

n = int(input())

def decimal(x) :
    dec_sum = []
    for i in range(1, x+1):
        if (x % i == 0):
            dec_sum.append(i)
    if len(dec_sum) == 2:
        return x
    else : 
        return None
    
cnt = 0

for i in range(1, n+1):
    
    if decimal(i) == i : 
        cnt += 1
    
print(cnt)

 

n = int(input())
num_list = [0]*(n+1)
# 리스트의 인덱스 번호와 숫자의 번호를 맞춰주기 위하여 (n+1)개의 원소를 가진 리스트 생성
cnt = 0

for i in range(2, n+1) :
	# 리스트의 원소가 0일때마다 하나씩 카운팅을 하고 
    if num_list[i] == 0 :
        cnt += 1
	# 그 원소가 0일때 해당 원소의 배수에 해당하는 인덱스의 원소를 1로 변경
    for j in range(i, n+1, i) :
        num_list[j] = 1

print(cnt)

 

 

나름 신박하게 잘 풀었다고 생각했는데... ㅠㅠ

time limit....