백준 4948번 파이썬

4948번: 베르트랑 공준

백준 4948번

최근에 소수찾기 문제들을 풀다가 4948번에서는 시간초과 때문에 한 번 틀렸다.

처음에 제출한 코드는

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

if __name__ == "__main__":
    ans = []
    while True:
        n = int(input())
        count = 0
        if n == 0:
            break
        else:
            for i in range(n + 1, (2 * n) + 1):
                if isPrime(i):
                    count += 1
            ans.append(count)
    
    for val in ans:
        print(val)

루트를 사용해서 시간 복잡도를 줄이긴 했지만, 입력 최대가 12만이 넘기 때문에 ( 만약 n이 12만 이면 12만번 * 최소 12만 제곱근 이상은 걸림-> 1억회 이상 연산수 발생 ) for문 중복을 써버리면 초과가 난다. 

 

그래서 다시 생각해낸 다른 방법은 입력 전에 모든 수가 소수인지 아닌지 배열로 초기화 시키는 것이다.

즉, 최대수까지 배열을 만들어 isPrime 함수를 이용해 소수인지 체크해서 값을 1로 할당한다.

그 다음 n이 입력 되면 배열에서 수를 가져와서 소수인지 확인하고 count를 증가시킨다.

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

if __name__ == "__main__":

    ch = [0] * 246913
    # ch 배열을 이용해서 최대 246912까지 소수인지 판별하여 할당. 
    for i in range(2, 246913):
        if isPrime(i):
            ch[i] = 1
   	
    while True:
        n = int(input())
        count = 0
        if n == 0:
            break
        else:
        # 소수인지 체크한 ch 배열을 이용해서 소수인지 확인
            for k in range(n + 1, (2 * n) + 1):
                if ch[k] == 1:
                    count += 1
            print(count)