Python - 소수 구하기

소수 : 1과 자기 자신으로만 나눠지는 수

예를 들어, 7은 1과 7로만 나누어 떨어지고 10은 2, 5로도 나누어 떨어지기 때문에 소수가 아님.

꽤나 자주 나오는 주제인데 할때마다 헷갈려서 정리하고 가자.

소수를 구할 최대 정수를 입력받고, 그 범위안에 소수가 어떤게 있는지 출력하는 알고리즘을 짤 것.

def isPrime(n): #소수 구하는 함수
    if n <= 1: #1이나 0은 False반환
        return False
    
    for k in range(2, n):
        if(n%k == 0): #입력받은수를 계속 증가하는 k로 나눠서 나머지가 없다? -> 소수x
            return False
    return True #계속 나눈결과 나머지가 0이 아니다 -> 소수o, print문에서 출
 
num = input("소수를 구할 최대 정수 :") #최대 정수 입력
num = int(num)
 
for k in range(num+1): #만약 15를 입력받았다면 15까지의 정수중에 소수있는지 구함(0~15)
    if isPrime(k): #소수 구하는 함수 호출
        print(k, end=" ") #isPrime이 True를 반환하면 실행