문제
거의 소수
교재 풀이
import java.util.Scanner;
public class P1456_거의소수 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long Min = sc.nextLong();
long Max = sc.nextLong();
long[] A = new long[10000001];
for (int i = 2; i < A.length; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(A.length); i++) { // 제곱근 까지만 수행
if (A[i] == 0) {
continue;
}
for (int j = i + i; j < A.length; j = j + i) { // 배수 지우기
A[j] = 0;
}
}
int count = 0;
for (int i = 2; i < 10000001; i++) {
if (A[i] != 0) {
long temp = A[i];
while ((double)A[i] <= (double)Max/(double)temp) {
if ((double)A[i] >= (double)Min/(double)temp ) {
count++;
}
temp = temp * A[i];
}
}
}
System.out.println(count);
}
}
내 풀이) 24.6.20에 풀다 만 풀이
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
Scanner sc=new Scanner(System.in);
long a=sc.nextLong();
long b=sc.nextLong();
long[] a=new long[10000001];
for(int i=2;i<=10000000;i++){
a[i]=i;
}
for(int i=2;i<=10000001;i++){
if(a[i]!=0){
for(int j=i*i;j<=10000001;j+=i){
a[j]=0;
}
}
}
long cnt=0;
for(int i=1;i<=10000001;i++){
long tmp=a[i];
while((double) a[i] < (double) b/tmp){
cnt++
tmp*=a[i]
}
}
}
}
소수의 n제곱이 거의소수
즉 2의 2제곱, 2의 3체곱 등등 => 4, 8이고
즉 3의 2제곱, 3의 3제곱 등등 -> 9, 27 등등
1번째 줄엔 범위 a, b가 주어짐
최대 각각 10의 14제곱이라.
출력은 거의 소수가 몇 개 있는지
접근법
에라토스테네스 응용문제
일단 교재 풀이 참고하면
10의 7제곱만큼 에라토스테네스의 체로 소수만 남긴 배열을 만들고
그 배열을 가지고 각각 max보다 작거나 같을 때까지 자기 자신의 m제곱을 해줘서
그 때마다 cnt++해주기
슈도코드
a,b를 입력받음: 범위 입력받음
long으로 받아야 함
에라토스테네스의 체로 10의 7제곱 크기의 배열 만들고
그 배열을 기존 에라토스테네스 체 구현하면 됨
즉 이중 for문인데, i=2부터 10000001까지,
if a[i] 값이 0이 아니면
for j=i*i, j<=b,j+=i
a[i]=0
다시 for문 돌려서
temp: a[i]
while a[i] < (double) max / temp
cnt+=
temp*=a[i]
cnt출력
설명
- 질문 1: temp = temp * A[i]; 부분에서 long 범위를 넘어가는지 여부
- 자바의 long 타입은 64비트 정수로, 범위는 -2^63에서 2^63-1까지입니다. 이 범위를 넘어가면 오버플로우가 발생합니다.
- temp가 A[i]의 거듭제곱을 계산하기 때문에, 큰 값의 경우 오버플로우가 발생할 수 있습니다. 그러나 이 코드는 temp가 Max를 넘는 경우에 while 루프를 종료하기 때문에, temp가 오버플로우를 발생시키는 상황은 방지할 수 있습니다.
- 오버플로우와 관련된 걱정을 해소하기 위해 일부 조건을 명확히 하고, 설명을 덧붙이겠습니다: => 아래 코드 제출했고 맞았음
import java.util.Scanner;
public class P1456_거의소수 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long Min = sc.nextLong();
long Max = sc.nextLong();
long[] A = new long[10000001];
// 에라토스테네스의 체를 이용하여 10^7 이하의 소수를 찾기
for (int i = 2; i < A.length; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(A.length); i++) { // 제곱근 까지만 수행
if (A[i] == 0) {
continue;
}
for (int j = i + i; j < A.length; j = j + i) { // 배수 지우기
A[j] = 0;
}
}
int count = 0;
// 거의 소수를 찾기
for (int i = 2; i < 10000001; i++) {
if (A[i] != 0) {
long temp = A[i];
while ((double)A[i] <= (double)Max / (double)temp) {
if ((double)A[i] >= (double)Min / (double)temp) {
count++;
}
if (temp > Long.MAX_VALUE / A[i]) { // 오버플로우 방지
break;
}
temp *= A[i];
}
}
}
System.out.println(count);
}
}
- 말씀하신 대로 A[i]가 10^7이라면, temp가 10^7로 초기화되고 temp *= A[i]가 실행되면 temp는 10^14가 됩니다. 이 경우 long의 범위를 초과하지 않지만, 그 이후 추가적인 곱셈이 있을 경우 long의 최대 값인 2^63 - 1을 초과하여 오버플로우가 발생할 수 있습니다.
- long 타입의 범위를 초과하는 경우를 방지하기 위해, temp를 A[i]로 곱하기 전에 항상 temp > Long.MAX_VALUE / A[i] 조건을 체크해야 합니다. 이 조건이 참이면 오버플로우가 발생할 가능성이 있으므로 루프를 종료합니다
- 질문 2: 왜 10^7까지만 다루는지
- 주어진 문제는 거의 소수를 찾는 문제입니다. 여기서 거의 소수는 "소수의 거듭제곱"을 의미합니다. 예를 들어, 22=42^2 = 422=4, 23=82^3 = 823=8, 32=93^2 = 932=9 등이 거의 소수에 해당합니다.
- 주어진 범위가 10^14까지인 이유는 거의 소수를 찾기 위해서는 소수의 거듭제곱이 그 범위 내에 존재해야 하기 때문입니다. 그러나 소수의 값 자체는 10^7 이하일 수 있습니다. 이는 다음과 같이 설명할 수 있습니다:
- 에라토스테네스의 체: 소수를 찾기 위해 에라토스테네스의 체를 사용하여 10^7까지의 소수를 찾습니다. 왜냐하면, 10의 14제곱의 제곱근은 01의 7제곱임. 따라서 10^7 이상의 소수는 10^14 이하의 거의 소수가 될 수 없습니다.
- 거의 소수 계산: 10^7 이하의 소수의 거듭제곱만 고려하면, 10^14 이하의 거의 소수를 모두 계산할 수 있습니다.
- 질문 3: (double)A[i] <= (double)Max / (double)temp에서 (double)을 붙이는 이유
- 이 코드는 A[i]와 Max / temp의 비교를 수행할 때 정밀도를 높이기 위해 double 형변환을 사용합니다. 정밀도가 높은 계산을 통해 정확한 결과를 얻기 위해 double 형변환을 사용합니다.
while ((double)A[i] <= (double)Max / (double)temp) {
// 중간 계산 생략
temp *= A[i];
}
- (double) 형변환을 사용하지 않을 경우, 두 long 값의 나눗셈에서 정수 나눗셈이 수행됩니다. 이는 소수 부분을 무시하게 되므로 정확한 비교가 되지 않을 수 있습니다. 따라서 double 형변환을 사용하여 실수 연산을 수행하고 정확한 비교를 수행합니다.