문제
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
베르트랑 공준은 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번 파이썬
백준 4948번 베르트랑 공준이번 문제는 n 부터 2n까지 소수를 구하는 문제 입니다.백준 1929번 소수 구하기이 문제는 위의 소수 구하기 문제에서 범위를 한정하는 것만 추가된문제입니다.해당 문제
velog.io
풀이
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보다 작거나 같은 소수가 리스트에 있으면 세는 방식이라는 얘기. …다음 파트도 혹시 시간제한 있음?
'BOJ > [BOJ] Python' 카테고리의 다른 글
| 백준 1085번 풀이 (0) | 2022.08.19 |
|---|---|
| 백준 9020번 풀이 (+응용편) (0) | 2022.08.19 |
| 백준 1929번 풀이 (0) | 2022.08.19 |
| 백준 11653번 풀이 (0) | 2022.08.19 |
| 백준 2581번 풀이 (0) | 2022.08.19 |
