에라토스테네스의 체2

• [백준] 1456번 : 거의 소수 C++ 문제풀이 솔루션 문제어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.입력첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.출력첫째 줄에 총 몇 개가 있는지 출력한다.제한1 ≤ A ≤ B ≤ 10^14 범위에 해당하는 모든 소수를 구해놓고 그 중 조건을 만족하는 수를 찾는 문제입니다.어떤 수는 N제곱(N>2) 꼴이므로 범위에 해당하는 수를 찾을 때 에라토스테네스의 체는 B의 제곱근 값 까지 사용하면 됩니다.수를 찾을 때 N제곱한 값이 long long 범위를 초과하여 오버플로우가 발생하는 경우가 있습니다.이를 방지하기 위하여 k^n>b 의 식을 i>b/k^(n-.. Algorithm/C++ 2024. 7. 8.

• 

  [백준] 1929번 : 소수 구하기 C++ 문제풀이 솔루션 문제M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.입력첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.출력한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.예제 입력 1 복사3 16예제 출력 1 복사3571113 주어진 정수 범위의 모든 소수를 구하는 문제입니다.에라토스테네스의 체를 사용하여 문제를 해결합니다.시간복잡도를 줄이기 위하여 외부 for문에서 N의 제곱근 까지만 탐색하고 값이 0으로 설정된 경우 탐색하지 않습니다.내부 for문에서 j의 제곱부터 탐색을 시작하여 j의 크기만큼 더해나가며 탐색하며 배수인 경우 값을 0으로 설정합니다.#include #include #incl.. Algorithm/C++ 2024. 7. 6.