[Python] 에라토스테네스의 체

> 과제 요구 사항

100000000 = 10^8 이하의 수를 입력하면, 입력한 수보다 작은 소수의 개수와 소수들 간의 차이 중 가장 큰 값을 출력한다.

> 출력 예시

Enter the number or type 'quit' : 10
There are 4 prime numbers less than or equal to 10, and 2 is the maximum separation
Enter the number or type 'quit' : 100
There are 25 prime numbers less than or equal to 100, and 8 is the maximum separation
Enter the number or type 'quit' : 500
There are 95 prime numbers less than or equal to 500, and 14 is the maximum separation

> 코드

while True:
    num=input('Enter the number or type \'quit\' :  ')
    
    if num.lower()=='quit':
        print('Good Bye~')
        break
    
    try:
        n=eval(num)
        a = [True] * (n + 1)
        m = int(n**0.5)
        cnt = 0
        sep = 0
        tmp = 0

        t=10
        for i in range(2, m + 1):
            if a[i] == True:
                for j in range(i + i, n + 1, i):
                    a[j] = False

        for i in range(2, n+1):
            if a[i]:
                cnt += 1
                if sep<i-tmp:
                    sep=i-tmp
                tmp=i

        print('There are {} prime numbers less than or equal to {}, and {} is the maximum separation'.format(cnt,n,sep))
    except:
        print('Invalid input - Input should be a positive integer.')

에라토스테네스의 체를 이용하면 소수가 몇 개인지 알 수 있다.
소수들 간의 간격을 아래 문서를 참고하여 코드로 작성하였다.
https://en.wikipedia.org/wiki/Prime_gap