에라토스테네스의 체

에라토스테네스의 체

소수를 판별하는 알고리즘.

소수를 대량으로 빠르고 정확하게 구하는 방법.

실제로 코테 문제를 푸는데 시간초과에 늪에 빠져서 이 방법으로 해결한다.

에라토스테네스의 체 원리

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2를 빼줘서 저장하면서 시작

3. 그 다음 모든 2의 배수를 제거 해준다.

4. 다음으로 3을 빼주면서 3에 대한 모든 배수를 제거해준다.

5. 4는 3번과정에서 지웠으므로 넘어가준다.

6. 5부터는 다시 5의 배수를 제거해준다.

코드

코드를 보기전에 간략하게 과정을 다시 설명하겠다.

우리가 해야하는건 한가지 숫자를 정하고 그 숫자에 대한 배수를 모두 지워가면서 거르고 거르는 것이다.

64로 예를 들면 루트 64인 8까지 배수들을 다 빼주면 64밑의 소수만 남게된다.

그래서 검사를 제곱급까지만 해도 알아서 다 걸러진다.

코드를 보자

def prime_list(n):
	remove = [True] * n
	
	m = int(n ** 0.5)
	for i in range(2, m+1):
		if remove[i] == True:
			for j in range(i+i, n, i):
				remove[j] = False
	return [i for i in range(2,n) if remove[i] == True]
	

이렇게 하면 좋을 줄 알았는데.... 이렇게 하면 2와 3을 출력하지 못한다. 따라서 조금 보완해줘야한다.

def prime_list(n):
    prime = [True] * n
    
    m = int(n**0.5)
    if n <= 3:
        prime[0] = False
        return [i+1 for i in range(n) if prime[i]==True]
    else :     
        for i in range(2, m+1):
            if prime[i] == True:
                for j in range(i+i, n, i):
                    prime[j] = False
        return [i for i in range(2,n) if prime[i] == True]
prime_list(3)

이러면 완벽한 코드라고 할 수 있겠다.

Uploaded by Notion2Tistory v1.1.0