[Algorithm] 37강 : 소수 판별 알고리즘의 정의와 구현

소수 판별 알고리즘

1.1 소수란?

• 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수다.
  • 6은 1,2,3,6 으로 나누어 떨어지므로 소수가 아니다
  • 7은 1과 7을 제외하고는 나누어 떨어지지 않으므로 소수이다.
• 코딩테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제 된다.

 

1.2 소수 판별 알고리즘 구현

# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
	# 2부터 (x-1)까지의 모든 수를 확인하며
    for i in range(2,x):
    	# x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
        	return False # 소수가 아님
    return True #소수임
    
print(is_prime_number(4))
print(is_prime_number(7))

 

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

• 2부터 x-1 까지의 모든 자연수에 대하여 연산을 수행해야 한다
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X) 이다.

 

 

 

약수의 성질을 이용한 소수 판별 알고리즘

 

2.1 약수의 성질

모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다.

이 조건으로 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근) 까지만 확인하면 된다.

 1 - 2 - 4 - 8 - 16

 

2.2 개선된 알고리즘

import math

#소수 판별 함수 ( 2이상의 자연수에 대하여)
def is_prime_number(x):
	# 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2,int(math(sqrt(x))+1):
    	#x가 해당 수로 나누어 떨어진다면
        if x % i ==0:
        	return False #소수가 아님
    return True # 소수
    
print(is_prime_number(4))
print(is_prime_number(7))

---

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.

참고 : www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC