判別基本アルゴリズム

に水を飲ませる

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

少数

素数判別基本アルゴリズム

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

薬性

約数の性質を利用してアルゴリズムを最適化する

に水を飲ませる

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

エラトステネスのふるい

実装を試みる

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