목록1456 (1)

승코딩당당당

[C++] 백준 1456: 거의 소수

문제[C++] 백준 1456: 거의 소수 GOLD 5https://www.acmicpc.net/problem/1456 접근 방법이 문제는 구간 [A, B] 안에 있는 거의 소수(= 어떤 소수 p에 대해 p², p³, p⁴ … 꼴인 수)의 개수를 세는 문제다.모든 수를 일일이 나눠보면 범위가 너무 커서 불가능하므로, "소수의 거듭제곱을 만들어서 세는 방식”으로 접근한다. 1. √B 까지의 소수 먼저 구하기어떤 거의 소수 p^k가 B 이하라면, 밑이 되는 소수 p는 반드시 p ≤ √B를 만족한다.그래서 먼저 2 ~ √B 범위에 대해 에라토스테네스의 체로 소수를 구한다.vector vect;for (LL i = 0; i 2. 각 소수 p에 대해 p², p³, p⁴… 생성해서 카운트i가 소수라면 i^2부터 ..
PS/BOJ 2026. 2. 10. 13:53
이전 Prev 1 Next 다음