[파이썬 실력 테스트] 13. 소수 판별하기, 특정숫자 소수 판별

●문제:

숫자를 입력하면 해당하는 숫자가 소수인지 아닌지를 판별하는 메세지를 출력하는 함수를 작성하시오

입력예시:

5

출력예시:

소수입니다.

 

 

---

import math

# 에라토스테네스의 체 알고리즘 
def prime(n):
    #0,1번째가 False이고 2부터 True인 배열을 생성
    #소수이면  True, 소수가 아니면 False로 바꿀 배열임
    array = [False,False] + [True]*(n-1)
    
    # 2부터 n의 제곱근(sqrt(n))까지의 모든 수를 확인
    for i in range(2, int(math.sqrt(n)) + 1):
        # i가 소수인 경우 (True인경우=지우고 남은 수인 경우)
        if array[i] == True:
            # i를 제외한 i의 모든 배수를 지우기
            j = 2 
            while i * j <= n:
                array[i * j] = False
                j += 1

    if array[n]==False:
        return ("소수가 아닙니다.")
    else:
        return("소수입니다.")

n = int(input())
print(prime(n))

5
소수입니다.

 

 

 

 

 

 

 

 

 

출처: 예제 중심 파이썬 입문

궁금한 부분이 있으면 댓글 부탁드립니다^^