[Python] 소수(Prime Number) 판정

• 1개의 수를 소수인지 판단하는 알고리즘

import math

# X >= 2

# 시간복잡도 : O(X), 1과 X사이의 숫자로 나누어지는지 확인
def is_prime_number(X):

	for i in range(2, X):
    
    	if X % i == 0:
            # 소수가 아님
        	return False
    
    # 소수
    return True

# 시간 복잡도 : O(X^(1/2)), 가운데 약수 기준 좌우대칭 성질 활용
def is_prime_number(X):

	for i in range(2, int(math.sqrt(X))+1):
    	
        if X % i == 0:
        	#소수가 아님
            return False
    
    return True

• 에라토스테네스의 체 : 주어진 수 X이하의 모든 소수를 구하는 알고리즘

import sys
import math

# 시간복잡도 : O(NloglogN), N < 1,000,000일 경우 사용

# 주어진 수 X
X = int(sys.stdin.readline().rstrip())

# 1 ~ X까지를 나타내는 리스트, True로 초기화
array = [True] * (X+1)

# 1은 소수가 아님
array[1] = False

# 소수판정
for i in range(2, int(math.sqrt(X))+1):

	if array[i]:
    
    	j = 2
        
        while i * j <= X:
        	
            # i의 배수 이므로 소수가 아님
        	array[i*j] = False
            j += 1

# 1 ~ X까지의 수 중 소수 출력
for i in range(1, X+1):

	if array[i]:
    
    	print(i)