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 | 31 |
Tags
- Python
- PS
- C++
- knapsack
- segment-tree
- Binary-Search
- codeup
- math
- backtracking
- lazy-propagation
- queue
- Greedy
- string
- implementation
- C
- DP
- Dijkstra
- Constructive
- ad_hoc
- Sort
- Prefix-Sum
- bruteforcing
- BFS
- sliding-window
- floyd_warshall
- number_theory
- priority_queue
- bitmask
- java
- stack
Archives
- Today
- Total
공작소
[ BOJ ] 1456 : 거의 소수 ( GOLD 5 ) / Python 본문
문제 링크 : https://www.acmicpc.net/problem/1456
문제
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.
입력
첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.
출력
첫째 줄에 총 몇 개가 있는지 출력한다.
풀이 과정
10^14 까지의 소수를 전부 구하려면 힘들 것이다...
다행히 우리가 구해야 하는건 어떤 소수의 N제곱이므로, 10^7 까지의 소수만 구해도 된다.
( 10^7 보다 큰 소수는 2제곱 했을 때 10^14를 초과한다. )
10^7 까지의 소수를 구한 뒤, 한 소수마다 B를 넘지 않을 때 까지 계속 제곱시키면서 A보다 크거나 같고 B보다 작거나 같은 거의 소수의 개수를 카운트 한다.
import sys
import math
input = sys.stdin.readline
a, b = map(int, input().rstrip().split())
arr = [1 for _ in range(10000001)]
arr[0] = 0
arr[1] = 0
for i in range(2, 10000001):
for j in range(i**2, 10000001, i):
arr[j] = 0
cnt = 0
for i in range(2, 10000001):
if arr[i] == 1:
now = i**2
while now <= b:
if a <= now: cnt += 1
now *= i
print(cnt)
'Problem Solving > BOJ' 카테고리의 다른 글
[ BOJ ] 6236 : 용돈 관리 ( SILVER 2 ) / Python (0) | 2024.03.22 |
---|---|
[ BOJ ] 2548 : 대표 자연수 ( SILVER 3 ) / Python (1) | 2024.03.22 |
[ BOJ ] 1929 : 소수 구하기 ( SILVER 3 ) / Python (0) | 2024.03.10 |
[ BOJ ] 16112 : 5차 전직 ( SILVER 2 ) / Python (0) | 2024.03.10 |
[ BOJ ] 25181 : Swap the elements ( GOLD 3 ) / Python (0) | 2024.02.17 |