알고리즘 - 코딩 테스트에서 자주 출제되는 기타 알고리즘(소수 판별 알고리즘)

 

 

✏소수 = 1과 자기 자신을 제외하고 나누어 떨어지지 않을 때 소수라고 한다.

#소수 판별 함수(1은 소수가 아니기때문에 2이상의 자연수부터)
def is_prime_number(x):

    #2부터  x-1 까지 모든 수를 확인하면서 소수 판별 진행
    for i in range(2,x):

        #x가 해당 수로 나누어 떨어지는 경우 소수가 아니기에 False 리턴해준다.
        if x%i == 0:
            return False

    #자기 자신과 1로만 나누어지는 수이기 때문에 소수 True 리턴
    return True

 

✏소수의 판별: 기본적인 알고리즘 성능 분석

- 2부터 x-1까지 모든 자연수에 대해서 연산을 수행해야 한다

    - 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(x)이고 x의 수에 비례해서 시간 복잡도가 늘어나게 된다.

 

 

 

 

 

import math

#소수 판별 함수(2이상의 자연수에 대해서)
def is_prime_number(x):
    
    #2부터 x의 제곱근까지 모든 수를 확인하며
    for i in range(2,int(math.sqrt(x))+1):
        if x % i == 0:
            return False
        
    return True

 

✏소수의 판별: 개선된 알고리즘 성능 분석

- 2부터 x의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대하여 연산을 수행한다.