Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 분할메모리할당
- 정렬
- 기초100제
- 스프링
- 리덕스장바구니
- 일상
- C++
- 프로그래머스
- Java
- error
- OS
- 자료구조
- 코드업
- web
- 공부
- react
- Operating System
- 토이프로젝트
- js to ts
- codeup
- 파이썬
- 협업
- Redux
- react-redux
- 백준
- memory
- 타입스크립트
- Spring
- CPU 스케줄링
- 알고리즘
Archives
- Today
- Total
감자튀김 공장🍟
[백준/4948] 베르트랑 공준 (with 파이썬) 본문
반응형
✔ 문제
✔ 풀이
nums = [] # 소수를 저장할 리스트
for i in range(2, 246913):
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
break
else:
nums.append(i)
while True:
n = int(input())
count = 0
if n == 0:
break
for i in nums:
if n < i <= 2*n:
count += 1
print(count)
✔ 설명
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구해야하는데 n을 입력받을 때마다 2n까지의 소수를 구하는 것은 시간이 굉장히 오래 걸린다.
그래서 2부터 246913의 범위에서 소수를 따로 배열에 미리 저장해 놓은 후 입력받은 n ~ 2n 사이의 소수가 배열에 얼마나 있는지 카운트하면 된다.
2부터 246913의 범위에서 소수를 찾는 이유는 n이 1부터 123,456까지 입력을 받을 수 있는 범위인데다 n~2n 사이의 소수를 구해야하기 때문이다. 그래서 1 * 2 <= n < = 123,456 * 2 + 1 범위에서 소수를 미리 찾아놓는 것이다.
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[백준/2738] 행렬 덧셈 (with 파이썬) (0) | 2022.11.03 |
---|---|
[백준/9020] 골드바흐의 추측 (with 파이썬) (0) | 2022.11.02 |
[백준/1929] 소수 구하기 (with 파이썬) (0) | 2022.10.31 |
[백준/11653] 소인수분해 (with 파이썬) (0) | 2022.10.30 |
[백준/2581] 소수 (with 파이썬) (0) | 2022.10.29 |
Comments