백준 4948번 풀이

문제

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

베르트랑 공준은 n부터 2n까지의 범위 중 적어도 소수가 하나는 있다는 얘기. 문제에서도 n을 입력하면 2n까지 소수가 몇 개 있는지를 출력한다.

 

Reference

https://velog.io/@iillyy/%EB%B0%B1%EC%A4%80-4948%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

백준 4948번 파이썬

 

풀이

def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 1: # 실수로 0 200으로 입력했더니 0이 소수로 나와버림
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

일단 이놈은 소수파트 끝날때까지 가져가는 게 맞다. 

import sys
def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 1: # 실수로 0 200으로 입력했더니 0이 소수로 나와버림
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True
while True: 
    P = []
    N = int(sys.stdin.readline())
    M = 2 * N
    if N == 0:
        break
    for i in range(N+1,M+1):
        if isprime(i):
            P.append(i)
    print(len(P))

일단 이렇게 해도 찾아는 준다. n부터 2n까지 isprime이라는 함수를 적용해서 소수면 리스트업하고, 최종 리스트 길이를 출력하는 건데… 이거 내면 뭐가 반기게요? 그렇죠… 응애 나 애기시간초과! 가 반겨요…

import sys
def isprime(a):
    sqrt = int(a ** 0.5)
    if a < 1: # 실수로 0 200으로 입력했더니 0이 소수로 나와버림
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True
while True: 
    P = 0
    N = int(sys.stdin.readline())
    M = 2 * N
    if N == 0:
        break
    for i in range(N+1,M+1):
        if isprime(i):
            P += 1
    print(P)

이것도 응애 나 애기시간초과! 뜬다… 깝깝하잖아여? 아니 이러시는 이유가 있으실 것 아니세요… 그래서 질문을 찾아봤는데 리스트를 만들고 거기서 가져오라길래 뭔 소린가 했음… 그러다가 참고문헌을 발견했음.

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

prime = []
for i in range(2,246912):
    if isprime(i):
        prime.append(i)

N = int(sys.stdin.readline())
while True:
    P = 0
    if N == 0:
        break
    for i in prime:
        if N < i <= 2 * N:
            P += 1
    print(P)
    N = int(sys.stdin.readline())

리스트를 만들고 가져오라는 건, n의 범위가 어쨌든 123456으로 정해져 있으니까 2n의 최댓값은 123456 * 2(246912)일거고, 그럼 거기까지 소수 리스트를 만들어 둔 다음 n을 입력받아서 n보다 크고 2n보다 작거나 같은 소수가 리스트에 있으면 세는 방식이라는 얘기. …다음 파트도 혹시 시간제한 있음?