[Math] 코딩테스트에 나오는 수학 정리(정수론 : 공약수/공배수, 에라토스테네스의 체..)

소수 판정

에라토스테네스의 체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

대상 정수의 제곱근보다 작은 정수들만 보면 충분하다.

입력받은 정수의 소수 여부 구하는 방법

https://freedeveloper.tistory.com/391

def is_prime(a:int) -> bool:
    for i in range(2, a):
        if a % i == 0: return False
        if i*i > a: break # 제곱근보다 큰 애들은 볼 필요 없으므로
    return True

• 소수 찾는 알고리즘

소수 리스트를 구하는 방법(에라토스테네스의 체)

소수 리스트가 필요하다면

n = int(input())
is_prime = [False, False] + [True]*(n-1)    # 0과 1은 소수가 아니다
primes = []

for i in range(2, n+1):
    if is_prime[i]:    # 만약 해당 숫자가 소수이면 소수 리스트에 추가한다.
        primes.append(i)
        for j in range(2*i, n+1, i):    # 그리고 해당 숫자(소수)의 배수들은 모두 소수가 아니다.
            is_prime[j] = False
print(primes)

• is_prime 리스트에 해당 인덱스의 숫자들의 소수 여부를 판단한다.
• 2부터 n까지의 정수들을 is_prime 리스트와 대조하면서 소수 여부를 판단한다.
• 만약 해당 정수가 소수라면 소수 리스트에 포함시킨다.
• 그 정수의 배수들은 모두 소수가 아님을 is_prime 리스트에 추가한다.

소수 리스트가 필요 없다면

n = int(input())
is_prime = [False, False] + [True]*(n-1)    # 0과 1은 소수가 아니다

sq = int(n**0.5)   # 해당 숫자가 소수인지의 판단은 숫자의 제곱근 이하까지만 보면 된다.
for i in range(2, sq+1):
    if is_prime[i]:    # 만약 해당 숫자가 소수이면 소수 리스트에 추가한다.
        for j in range(2*i, n+1, i):    # 그리고 해당 숫자(소수)의 배수들은 모두 소수가 아니다.
            is_prime[j] = False
print(is_prime)