미리 알아가자.
1. 소수 판별 알고리즘
특정 N이 소수인지 아닌지 판별
특정 수가 소수인지 아닌지 알아 보려면
for문을 써야한다!
# 소수 판별 함수
ef is_prime_number(n):
end = int(n**(1/2))
for i in range(2, end+1):
if n % i == 0:
return False
return True
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
약수의 성질을 생각했을 때 약수(제곱근)까지만 확인하면 된다.
- 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
- 예를 들어 16의 약수는 1, 2, 4, 8, 16이다
- 이때 2 X 8 = 16은 8 X 2 = 16과 대칭이다
- 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다
2. N까지 수에서 소수들 뽑기(에라토스테네스의 체)
def get_primes(N):
array = [True for _ in range(N+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
# 에라토스테네스의 체 알고리즘
end = int(N**(1/2))
for i in range(2, end+1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
j = 2 # i를 제외한 i의 모든 배수를 지우기
while i*j <= N: # 배수들 제거
array[i*j] = False
j += 1
return [i for i in range(2, N+1) if array[i]]
primes_list = get_primes(100)
print(primes_list)
