[코테] 소수판별

자연수n이 주어질 때, n 이 소수인지 판별하는 프로그램을 작성하여라.

• 기본 생각대로 작성한 코드
  앞에서부터 나누어 떨어지는 경우 count 를 하고 그게 2개보다 큰 경우는 소수가 아님. n 까지 반복했는데 나누어 떨어지는 경우가 2번일 경우 (1과 자기 자신이 되겠지) 는 소수로 판별.
  

n = int(input())
count = 0

for i in range(1,n+1):
  if n % i == 0:
    count += 1
    if count > 2 :
      print('NO')
      break
    elif (i == n) and (count == 2):
      print('YES')
      break
        

• 2이상의 수로 나눠 떨어지는 경우가 있으면 소수가 아님.

n = int(input())
result = 'YES'
for i in range(2, n):
  if n % i == 0:
    result = 'NO'
print(result)

• 위에 코드를 함수로 만든 소수판별함수

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

• math library 사용하는 경우
  num 에 +1 을 하고 루트를 씌워서 내림한 수까지 반복문 사용 (절반만 검사해도 소수인지 판별 가능)

import math 

num = int(input())
result = "YES"
for i in range(2, math.floor(math.sqrt(num+1))):
  if(num % i == 0):
    result = "NO"
    break
print(result)

• 에라토스테네스의 체 알고리즘 사용하는 경우
  시간 복잡도가 O(NloglogN) 으로 다른 방법들보다 빠르지만 메모리가 많이 필요하다.

# -*- coding: utf-8 -*-
# 에라토스테네스의 체 구현
import math

n = 5 # 2부터 1000까지의 모든 수에 대해 소수 판별

# 모든 수가 소수인 것으로 초기화 (True)
array = [True for i in range(n+1)]

# 2부터 n의 제곱근까지의 모든 수 확인
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=' ')