[Algorithm]소수 찾는 알고리즘

소수의 정의는 '1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수'

 

 

 

2부터 (x - 1)까지의 모든 수로 중 하나라도 나누어떨어진다면

def isPrime(x):

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

 

알고리즘 성능 

• 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는

 

약수의 성질을 이용한 개선 알고리즘을 만든다. 

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
  • 예를 들어 16의 약수는 1, 2, 4, 8, 16 에서  2 X 8 = 16은 8 X 2 = 16과 대칭이다

 

 

• 따라서 우리는 특정한 자연수의 자연수의 제곱근까지만 확인하면 된다
  • 예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다.

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

알고리즘 성능 

시간 복잡도는

 

참조 freedeveloper.tistory.com/391