728x90 반응형 거의 소수1 [백준] 1456번 : 거의 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 구한 소수들의 N제곱값이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다. 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 최대로 소수를 탐색해야 하는데 에라토스테네스의 체를 이용하여 빠르게 소수를 먼저 구한다. 이후 구한 소수들의 N제곱값이 A와 B 범위 안에 존재하는지 판별해 거의 소수의 개수를 구하면 문제를 해결할 수 있다. 슈도코드 A(시작 수).. 2024. 1. 26. 이전 1 다음 728x90 반응형
