백준 2581 - 소수 찾기

2020-12-21

소수 찾기(에라토스테네스의 체)

에라토스테네스의 체 : 찾고자 하는 수(n)까지 True로 채운 후 리스트를 만들고, 2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수… sqrt(n)의 배수를 모두 False로 바꾼다. 결국 2~n까지 숫자 중 True인 숫자들이 소수가 된다.

def prime_list(n):
  # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수 간주)
  prime = [True] * n

  # n의 최대 약수는 sqrt(n) 이하이므로, 검사 최대값(i)은 sqrt(n)+1, 즉 sqrt(n)까지 검사.
  m = int(n ** 0.5)
  for i in range(2, m + 1):
    if prime[i] == True: # i가 소수인 경우
      for j in range(i+i, n, i): # i 이후 i의 배수들을 False로 판정
        prime[j] = False
  # 소수 목록 산출
  return [i for i in range(2, n) if prime[i] == True]

print(prime_list(10))

소수인가, 아닌가

def checkPrime(n):
  m = int(n ** 0.5)
  isPrime = True
  if n == 1:
    isPrime = False
  else:
    for i in range(2, m+1):
      if n % i == 0:
        isPrime = False
  return isPrime