Python : 에라토스테네스의 체

참고

일반적으로 소수를 구하는 함수

• 시간 복잡도 : O(n)

def isPrime(a):
    if a < 2:
        return False

    for i in range(2, a):
        if a % i == 0:
            return False
    return True

인자의 제곱근까지만 살펴보고 판별하는 함수

• 인자의 제곱근까지만 봐도 소수 판별이 가능하다.
• 시간 복잡도 : O(x^(1/2))

import math

def isPrime(x):
	for i in range(2, int(math.sqrt(x))+1):
    	if x % i == 0:
        	return False
    return True

에라토스테네스의 체

• 시간 복잡도 : O(n log log n)

1. 2부터 N까지 모든 자연수를 소수로 초기화한다.

   array = [True for i in range(n+1)]

2.n의 제곱근까지 모든 수를 확인하면서 소수인 수를 확인한다.

for i in range(2, int(math.sqrt(n)+1))
    	if array[i] == True:

3. 발견한 소수인 array[i]에서 i의 배수는 소수가 아니므로 모두 False로 변경한다.

        	j = 2 # j= 2배수 3배수 4배수...<= n
            while i * j <= n:
              array[i*j]= False
              j+=1

4. 2~3반복

import math

def is_prime_number(n):
	array = [True for i in range(n+1)]
    
    for i in range(2, int(math.sqrt(n)+1))
    	if array[i] == True:
        	j = 2
            while i * j <= n:
              array[i*j]= False
              j+=1
    return [ i for i in range(2, n+1) if array[i]]