[01-2] 소수를 구하는 알고리즘

1. 알고리즘

"C로 배우는 알고리즘"은다음과 같이 알고리즘을 표현합니다.

1. 정수 N을 입력받는다.

2. 정수 i에 2를 대입한다.

2.1 N이 i로 나누어 떨어지는가? (% 연산자를 사용)

2.1.1 나누어 떨어지면 소수가 아니다. 끝

2.2 i를 하나 증가시킨다.

2.3 i가 N보다 작은가?

2.3.1 작으면 2.1로 돌아간다.

3. 정수 N은 소수이다. 끝

2. 동작 코드

이를 코드를 작성하였습니다.

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

개선을 위해서 모든 숫자에 대해서 검사하지 않고, sqrt()를 이용해서 범위를 줄였습니다.

def is_prime2(n):
    sqrn = int(math.sqrt(n))
    for i in range(2, sqrn+1):
        if n % i == 0:
            return False
    return True

3. 실행 코드

실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-5 : PRIME2.C에 대응)

def print_results(i, n, r, t):
    if r:
        print('Test case', i, ":", n, "is prime in", t)
    else:
        print('Test case', i, ":", n, "is not prime in", t)


# Main function
LOOP = 10000

print("Test input number is prime or not")
print("Input 0 to end program")

while True:
    print()
    input_data = int(input("Input number to test -> "))

    if input_data < 0:
        print("Please input positive integer")

    if input_data == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime(input_data)
    end_time = time.process_time()
    print_results(1, input_data, test_result, end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        test_result = is_prime2(input_data)
    end_time = time.process_time()
    print_results(2, input_data, test_result, end_time-start_time)

4. Tips

1. is_prime2()에서 for loop의 range에 +1을 사용해야 합니다.

5. 예제 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_01/Ch_01_2.py