소수(Prime Number)

2보다 큰 자연수 중에 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

판별

• 직접 나눔
• 약수의 대칭성 활용
• 에라토스테네스의 체 사용

직접 나눔

def is_prime_number(x):
  for i in range(2,x):
    if x % i == 0:
      return False
  return True

약수의 대칭성 활용

import math
def is_prime_number(x):
  for i in range(2, int(math.sqrt(x))+1):
    if x % i == 0:
      return False
  return True

장점
시간복잡도를 직접 나눴을 때 O(N)이었던 것을 O(N^1/2)까지 줄일 수 있음
단점
많은 수를 하나씩 검사하는 문제에서는 느릴 수 있음

에라토스테네스의 체

import math
array= [True for i in range(n+1)]
for i in range(2, int(math.sqrt(n)) + 1):
  if array[i] == True:
    j= 2
    while i*j <= n:
      array[i*j]= False
      j+= 1
for i in range(2, n+1):
  if array[i]:
    print(i, end=' ')

장점
O(NloglogN)의 시간복잡도를 가져 다수의 소수를 찾아야 하는 문제에서 자주 사용
단점
큰 메모리 공간을 차지 => n이 1,000,000 이내로 주어지는 경우가 많음