소수 (Prime Number)

1. 소수

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

---

2. 소수를 판별하는 방법

1. 모든 수 확인

def isPrimeNum(n:int)->bool:
    for i in range(1, N+1):
        if N % i == 0:
            return False
    return True

 

2. $\sqrt{N}$ 까지 확인

• $\sqrt{N}$까지 확인하면, 제곱근을 포함한 N을 나눌 수 있는 수 모두를 확인할 수 있다.

def isPrimeNum(N:int)->bool:
	for i in range(2, int(N**0.5)+1):
    	if N % i == 0:
        	return False
	return True

---

3. 소수를 찾는 방법 - 에라토스테네스의 체

• 특정 범위 내의 소수를 전부 찾는 경우, 위 방법을 활용하면 매우 긴 시간이 소요될 수 있다.
• 자신의 배수를 지워나가는 방법을 통해, 1과 자기 자신을 제외한 약수를 가진 모든 수(합성수)를 지워나간다.

에라토스테네스의 체 구현 과정 (출처- 위키백과)

# N까지의 모든 소수 구하기

def FindPrimeNumber(N:int)->list:
    prime_number_checklist = [False, False] + [True] * (N-1)
    prime_number = []

    for i in range(2, N+1):
        if prime_number_checklist[i] is True:
            prime_number.append(i) # 소수 넣기
            for num in range(2*i, N+1, i): # 합성수 모두 False로 만들기
                prime_number_checklist[num] = False
    return prime_number