[Python] 소수구하기 - 에라토스테네스의 체

소수 : 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수를 의미

 

📝 1부터 100사이의 소수구하기 코드구현

📝 에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배소룰 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

n = 100

a = [False, False] + [True]*(n-1)
primes=[]

for i in range(2, n+1):
	if a[i]:
    	primes.append(i)
        for j in range(i*2, n+1, i):
        	a[j] = False
print(primes)