백준 4948 풀이 (python3 시간초과)

별게 없다 N< ~ <=2N사이의 소수의 개수를 구하라는 문제다.

그나마 소수를 빨리 구하는 방법은 에라트뢍러낭ㄹ의 체를 사용하는 것이라 생각해서 이를 토대로 코드를 구현했다.

def check(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return 0
    return 1*(num!=1)
while(1):
    a = int(input())
    if a == 0:
        break
    sum = 0
    for val in range(a+1,(a*2)+1):
        if check(val):
            sum+=1
    print(sum)

 

 

코드는 별게 없다. 문제는 python3로는 시간초과가 난다. 그래서 꼼수인 pypy3로 제출을 하면 시간초과가 걸리지 않고 답을 제출가능하다.

 

다른 사람들의 코드를 보면 더 간단한 방법으로도 가능했다. 

예를들어

1. 입력 조건 1 ≤ n ≤ 123,456 에 맞추어 미리 소수들을 전부 구한다.

2. n에 맞추어 1 ≤ n ≤ 123,456 사이에 존재하는 소수들만 뽑아서 len()함수로 출력

=> 해당 방법을 통해 미리 구해진 소수를 사용하여 소수를 빠르게 뽑을 수 있다.