에라토스테네스의 체

에라토스테네스의 체(sieve of Eratosthenes)

---

1. 고대 그리스 수학자인 에라토스테네스가 고안한 소수를 찾는 방법으로 체로 치듯 수를 걸러낸다는 뜻으로 에라토스테네스의 체라고 불린다고 합니다.
   f(x) = x / (1p(x)) 의 수열을 표로 시각화

※ 1p(x) -> x가 소수일 경우 1, 그렇지않을 경우 0의 값을 가지는 지시함수

2. 방법

• 임의의 자연수 n에 대하여 그 이하의 소수를 모두 찾는 가장 간단하고 빠른 방법

  1. 1부터 100까지 숫자를 작성합니다.

     

  2. 자연수 1을 제거합니다. (1은 소수, 합성수도 아닌 유일한 자연수)

     

  3. 소수인 2를 제외한 2의 배수를 제거합니다.

     

  4. 소수인 3을 제외하고 3의 배수를 제거합니다.

     

  5. 4의 배수는 앞서 2의 배수로 지워졌기 때문에 소수인 5를 제외하고 제거합니다.

     

  6. 소수인 7을 제외하고 제거합니다.

     

---

Python 코드

def sieve_of_Eratos(n):
    prime = [True for _ in range(n+1)]
    p = 2
    while (p * p <= n):
    	# 만약 p값이 소수일 경우를 확인
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
            	# p의 제곱부터 시작해서 n+1까지 p만큼 증가하면서 p의 배수들을 제거합니다.
                prime[i] = False
        p += 1
    
    prime_numbers = []
    for p in range(2, n+1):
        if prime[p]:
            prime_numbers.append(p)
    return prime_numbers

code by other

# 1001까지 소수 확인하기
check_prime = [True for _ in range(1001)]

# 0과 1은 소수가 아니므로 제외하여 2부터 시작
for i in range(2, 1001):
	# 만약 check_prime값이 True 일 경우
	if check_prime[i] == True:
    	# 2의 배수, 3의 배수, 4의 배수(2의 배수에서 제외하였음)
        # 5의 배수 ... 을 순차적으로 제거합니다.
    	for j in range(2*i, 1001, i):
        	check_prime[j] = False

Python by 나무위키

def eratosthenes(num:int = 1000000):
    MAX = num + 1
    LIM = int(num ** 0.5) + 1
    RSET = lambda strt, end, gap: set(range(strt, end, gap))
    
    # 5 (mod 6)과 1 (mod 6)을 참으로 설정한다. 이들은 2의 배수도 아니고 3의 배수도 아닌 숫자집합이다.
    # 단, 1은 소수가 아니기에 1 (mod 6)은 7부터 시작한다.
    prime = RSET(5, MAX, 6) | RSET(7, MAX, 6)
    if num > 2: prime.add(3) # 3 추가
    if num > 1: prime.add(2) # 2 추가
    for i in range(5, LIM, 6):
        # 5 (mod 6) 부분
        if i in prime:
            prime -= RSET(i * i, MAX, i * 6) | RSET(i * (i + 2), MAX, i * 6)
        # 1 (mod 6) 부분
        j = i + 2
        if j in prime:
            prime -= RSET(j * j, MAX, j * 6) | RSET(j * (j + 4), MAX, j * 6)

    return prime

---

출처: 나무위키