[백준 파이썬 4134번] 다음소수 모든 풀이 비교 분석

문제

배경지식

이 문제의 경우 소수를 찾는 문제이기 때문에 우선 수가 주어졌을 때, 그 수가 소수인지부터 확인하는 판별법을 알고 구현해야 한다.
소수 판별법에는 여러 방법이 있지만 에라토스테네스의 체와 직접 나누어보는 방법이 가장 널리 알려져 있다. 관련된 이론적 배경은 이 단계 내에서 많이 사용되기에 따로 다루어 보았다.

https://aaaaaaaaaaayowooji.tistory.com/31

[파이썬과 알고리즘] 소수 판별 알고리즘(에라토스테네스의 체, 직접 나누기)

 

 

논리 및 아이디어

기본적인 문제 풀이 구조는 간단했다.

1. 처음에 몇 개의 수가 주어질지 입력된다. 이를 입력받아서 숫자만큼 반복문을 통해 반복해 주면 된다.
2. 반복문 내에서 기준 숫자를 입력받는다.
3. 기준 숫자부터 1씩 더해가며 그 숫자가 소수면 출력하고 아니라면 다음 수로 넘어간다.

어떤 정수가 주어졌을 때, 소수인지 판별하는 함수를 짜는 것이 관건이었다.
소수는 짝으로 존재하기 때문에 모든 수에 대해서 나눠볼 필요가 없고 $\sqrt N$까지만 나눠보는 것이 핵심이었다.

나의 코드

def isprime(num):
    start=2

    while 2<=start<=num**0.5:
        if num%start==0:
          return False
        start+=1
    return True

num=int(input())
for _ in range(num):
    test= int(input())
    while True: 
        if isprime(test):
            print(test)
            break
        else:
            test+=1

실행결과

틀렸다...

최적의 코드

vscode에서 앞선 '나의 코드'를 실행해보았을 때, 잘 실행되어서 무엇이 잘못되었는지 찾을 수 없었다.
게시판을 뒤적거리다 누군가 0과 1에 대해서 반례를 들었고 나의 코드가 틀렸음을 알았다.

0과 1의 반례에 대해서는 간단하게 if문을 사용해서 0과 1이 입력되면 2를 반환하는 것으로 해결했다.

def isprime(num):     #소수인지 판별하는 함수. 소수면 True를 반환. 아니면 False를 반환
    start=2

    while 2<=start<=num**0.5:  #루트N까지만 나누어보는 것이 시간단축의 핵심
        if num%start==0:      #나눠지면 합성수이므로 False를 반환
          return False
        start+=1
    return True

num=int(input())
for _ in range(num):
    test= int(input())
    while True: 
        if test==0 or test==1:  #0과 1이 입력되면 2를 출력
            print(2)
            break
        if isprime(test):       #소수라면 출력
            print(test)
            break
        else:
            test+=1            #소수가 아니면 1을 더해서 다시 수행

실행 결과

2072ms 소요되었다.

다른 정답 코드

에라토스테네스의 체를 사용?

다른 더 좋은 코드들이 있을지 고민해보았다. 정수의 범위가 $4\times10^9$이기 때문에 '오히려 에라토스테네스의 체를 이용하여 한번에 소수들을 찾아놓고 가져다 출력할까?'라는 생각도 해보았다. '기존의 코드는 입력된 수가 $1\times 10^8$라면 $10^4$까지 나누어 봐야 하기 때문에 방법을 바꾸면 어떨까?'라는 생각이 들었던 것이다.

검색을 하던 중 이미 에라토스테네스의 체로 $4\times10^9$까지 소수를 다 찾아놓고 해봤더니 시간초과가 떴다는 후기를 발견했다. 모두 찾는 방식은 2의 배수를 지우기 위해서만 해도 $2 \times 10^9$번 메모리에 접근해 값을 변경해야 하기 때문에 당연한 것일지도 모른다.(에라토스테네스의 체를 구현할 때 딕셔너리로 범위 내의 모든 수를 key로, value로는 0과 1을 두어 지워나가는 방식을 사용해 구현한다면... )

다른 코드

다른 코드로 0과 1에 대한 처리를 함수에 넣은 사람들도 많았다.
함수에 0과 1을 처리하는 부분을 넣어서 다시 코드를 작성했다.

def isprime(num):
    if num == 0 or num == 1:   #0과 1을 처리
        return False
    elif num == 2:
        return True

    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    else:
        return True

num=int(input())
for _ in range(num):
    test= int(input())
    while True: 
        if isprime(test):      
            print(test)
            break
        else:
            test+=1  ...? 2000ms 가 갑자기 400ms로 실행시간이 확 줄었다.

실행 결과

424ms 걸렸다?

함수에 0과 1 처리하는 부분을 넣었다고 바뀔 거 같진 않아서 기존 함수 내 while문을 for문으로 작성하고 0,1 처리는 기존처럼 작성하고 제출해보았다.

코드

def isprime(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    else:
        return True

num=int(input())
for _ in range(num):
    test= int(input())
    while True:
        if test==0 or test==1:
            print(2)
            break
        if isprime(test):
            print(test)
            break
        else:
            test+=1

실행 결과

432ms 소요되었다.

왜 while문이 for문보다 느릴까?

조사를 해보아도 while문이 for문에 비해 느리다는 글을 찾기 힘들었다.

하나의 블로그에서 while문과 for문을 리스트의 요소에 접근하는 것으로 실험하는 글을 찾았는데 이 글에서는 while문이 for문에 비해 현저히 느렸다고 결론 내렸다.
그 이유로는 for문은 range객체를 한 번 생성하면 그 안의 값을 순차적으로 받아서 i에 저장하면 되지만 while문의 경우 i에 1씩 더하는 연산을 계속해야 해서라고 한다.
해당 블로그의 출처는 아래에 링크를 걸어놓았으니 궁금하신 분들은 찾아보시길...

내가 작성한 두 코드의 함수 부분에서 for문과 while문에 있는 연산도 같기 때문에 반복문 내부가 달라서라고 하기에는 무리가 있다. 아마 블로그에서 추측한 이유가 맞는 것 같다.

배운 점 및 보완할 점

1. 반복문을 사용할 때, 반복문 내 코드가 같다면 while문보다는 for문을 사용하는 편이 최적화에 유리함을 알 수 있었다.

출처

백준 홈페이지 4134번
원본 출처: Contest > Waterloo's local Programming Contests > 15 July, 2012 B번
파이썬 while문이 for문보다 느린 이유