판별 기본 알고리즘

약수

def check_divisor(nums):
	divisors = []
	for i in range(1, nums+1):
    	if nums % i == 0:
        	divisors.append(i)
    return divisors

소수

1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수이다.

• 4는 약수로 1,2,4를 가지므로 소수가 아니다.
• 7은 약수로 1과 7만을 가지므로 소수이다.

소수 판별 기본 알고리즘

def check_prime_number(nums):
	for i in range(2,nums):
    # 2 이상의 자연수인 nums에 대해 반복문을 돌며 nums-1까지 일일히 확인해
    	if i % nums == 0:
        	return False
        # i가 nums와 나누어 떨어지면 nums는 소수가 아님
    return True

약수의 성질

n이 자연수 일 때, a * b = n을 만족하는 자연수 a와 b가 존재한다고 가정해보자. 또한 n = m * m인 m이 있다면 a * b = m * m이 성립할 수 있다. 이 상태에서 a와 b가 자연수이려면 다음 세 경우 중 하나여야 한다.

1. a = m, b = m. 즉 a = b
2. a > m, b < m
3. a < m, b < m

a와 b가 자연수기 위해선 항상 위의 세 가지 사례 중 하나일 것이고 그렇다면 min(a,b) <= m일 것이다. 즉, a와 b 중 작은 숫자는 항상 m 즉 n의 제곱근보다 작거나 같다는 소리다.

이 원리를 이용하면 굳이 nums 범위 전체를 확인할 필요 없이 nums의 제곱근까지만 확인해도 약수를 찾거나 소수 판별을 할 수 있다는 말이다.

약수의 성질을 이용한 알고리즘 최적화

약수

def check_divisor(nums):
    divisors = []
    for i in range(1, int(nums**0.5) + 1):
        if nums % i == 0:
            divisors.append(i)
            if i != int(nums/i):
                divisors.append(int(nums/i))
    return sorted(divisors)

소수

def check_prime(num):
    if num == 1: return False # 1은 소수가 아니므로 제외
    
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False

    return True

에라토스테네스의 체

소수를 판별하는 다양한 알고리즘 중 임의의 자연수 n 이하의 특정 범위 내에서 소수를 찾는 가장 빠르고 간단한 방법이다.

120 이하의 자연수들 중 소수를 찾는 것을 예시로 들어보자.

원리는 다음과 같다.

1. 우선 소수도, 합성수도 아닌 유일한 자연수 1은 소수가 아니므로 제거한다.
2. 다음 숫자인 2 역시 소수이므로 소수로 체크하고 배열에서 2의 배수들을 제거한다.
3. 다음 숫자를 확인해 앞의 단계에서 제거되지 않았으면 소수로 체크하고 해당 숫자의 배수들을 제거한다. 120의 제곱근까지 해당 과정을 반복한다.

구현해보기

def prime_number(num):
    # 0부터 num 범위의 자연수의 소수 판별 여부를 위한 리스트. 
    # 0과 1은 소수가 아니므로 False로 선언
    check_prime = [False, False] + [True] * (num - 1)

    # 앞서 설명한 약수의 원리를 응용해 소수 판별 범위 축소
    for i in range(2, int(num**0.5)+1):
        if check_prime[i]:
            # i가 소수라면 i 이후 나올 i의 배수들은 전부 소수가 아니므로 False 선언
            for j in range(i+i, num+1, i):
                check_prime[j] = False

    return [i for i in range(2, num+1) if check_prime[i]]
    
print(prime_numbers(131))
>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131]

reference

[이것이 코딩 테스트다 with Python] 37강 소수 판별 알고리즘 - Youtube
[이것이 코딩 테스트다 with Python] 37강 소수 판별 알고리즘
[C++] 최적의 소수찾기, 에라토스테네스의 체
[내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체)
소수판별 알고리즘 - 파이썬(Python)
에라토스테네스의 체 (소수구하기. 파이썬)