11.(1) 소수 판별 알고리즘(에라토스테네스의 체) - 기타 알고리즘

소스코드(시간복잡도 O(X))

def oldIs_prime_number(x): #시간복잡도가 X
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2,x):
        #x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False #소수가아님
        return True #소수임

 

시간복잡도 개선하기

개선된 소스코드(시간복잡도 X의 1/2승)

def newIs_prime_number(x): #시간복잡도가 N의 1/2승
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2,int(math.sqrt(x))+1):
        #x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False #소수가아님
        return True #소수임
  
print(newIs_prime_number(4)) #소수아님
print(newIs_prime_number(7)) #소수임

 

이러한 개념을 이용하여 자연수 2~N까지의 소수여부를 시간복잡도를 개선하여 판별할 수 있다.

소스 코드

import math

n = 1000 #2부터 1,000까지의 모든 수에 대하여 소수 판별
#처음엔 모든 수가 소수(True)인 것으로 초기화(0,1은 제외)
array = [True for i in range(n+1)]

#에라토스테네스의 체 알고리즘 수행
#2부터 n의 제곱근까지의 모든 수를 확인하며
for i in range(2,int(math.sqrt(n)+1)):
    if array[i] == True: #i가 소수인 경우(남은 수 인겅우)
        #i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

#모든 소수 출력
for i in range(2,n+1):
    if array[i]:
        print(i,end=' ')

-> 단 하나의 소수를 구하는 문제라면 에라토테네스의 체 보다는 단순히 상위의 시간복잡도를 개선한 소수판별알고리즘만 사용하면 된다.