알고리즘 공부 Part3 : 소수 구하기

evasioner (42)in #kr-study • 7 years ago (edited)

예제는 파이썬으로 작성하였습니다.

알고리즘 공부 Part3 : 소수 구하기

소수의 정의

1과 자기자신 외에 나누어 떨어지는 정수가 없는 양의 정수

예를 들어 0 이상의 2,3,5,7,11,13 같은 수를 의미합니다.

특정 숫자(N)가 소수인지 판별하는 프로그램을 개발한다고 할때

2부터 N -1까지 정수로 나눠 떨어지는 수가 있는지 없는지 확인 하여 소수인지를 판별하게 됩니다.

정수로 나누어 떨어지면 소수가 아니고 나누어 떨어지지 않으면 소수입니다.

소수 구하기 코드 작성

코드를 작성해 봅시다.

소수를 입력 받아 입력받은 숫자가 소수인지 판별하는 코드를 작성해 봅시다. 코드는 아래 와 같습니다.

def isPrime(input) :
    for i in range(2, input -1) :
        result = input % i
        if result == 0:
            return False
    return True

if __name__ == '__main__':
    input = input()
    prime = isPrime(input)
    if prime == True :
        print("Prime")
    else :
        print("Not Prime")

%연산자를 이용하여 반복문을 이용하여 2부터 N-1까지 정수로 나눈후 나머지가 있는지 없는지를 비교합니다.
N-1까지 나누는 동안 모든 수로 나눠지지 않으면 소수입니다.

소수인지 판별하는 코드를 작성해 보았습니다. 하지만 이 코드도 개선할 포인트가 있습니다.

소수를 구하는 방법을 바꾸는 것이 아닌 소수를 구하는 i의 범위를 줄이는 것입니다.

소수 구하기 코드 개선

위코드로는 10이라는 숫자가 소수인지 판별하기 위해서 2부터 9까지 나눠봐야합니다. 만약 제곱근까지만 나누면 어떻게 될까요?

10은 2x5, 5x2 두가지 조합만 가집니다. 이를 통해 제곱근까지만 나눈다면 실행횟수를 줄일수 있습니다.

import math

def isPrime(input) :
    sqrn = int(math.sqrt(input))
    for i in range(2, sqrn) :
        result = input % i
        if result == 0:
            return False
    return True

if __name__ == '__main__':
    input = input()
    prime = isPrime(input)
    if prime == True :
        print("Prime")
    else :
        print("Not Prime")