[백준/JAVA] 1456번: 거의 소수

🔺 문제

1456번: 거의 소수

 

 

🔺 코드

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        long Min = Long.parseLong(st.nextToken());
        long Max = Long.parseLong(st.nextToken());
        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 += i) {    // 배수 지우기
                A[j] = 0;
            }
        }
        
        
        int cnt = 0;
        for(int i = 2 ; i < A.length ; i++) {
            if(A[i] != 0) {
                long tmp = A[i];    // 현재 소수
                
                // 🔔 소수를 N제곱한 값이 B보다 커질 때까지 반복문 실행
                while((double)A[i] <= (double)Max / (double)tmp) {
                    if((double)A[i] >= (double)Min / (double)tmp) {    // 🔔 소수를 N제곱한 값이 M보다 크거나 같으면 => 거의 소수
                        cnt++;
                    }
                    
                    tmp *= A[i];
                }
            }
        }
        System.out.println(cnt);
    }
}
 

✅ 해결 아이디어
✔ 에라토스테네스의 체

 

💥 유의사항

⇨ (반복문 범위) 10의 14제곱의 제곱근인 10의 7제곱까지 반복

⇨ N제곱한 값을 구하다가 범위가 long형을 초과하는 경우가 발생하므로 이항 정리로 처리

    -  (N의 k 제곱) vs B가 아닌, N vs B / (N의 k-1 제곱)으로 비교 (37,38번째 줄)

 

---

🔺 다른 풀이들

[백준] 1456 : 거의 소수 - JAVA

[JAVA 순환 알고리즘] 백준 알고리즘 1456번 / 거의소수 찾기

 

 

https://www.acmicpc.net/source/29360286

로그인

---

💬 느낀 점

37,38번째 줄 처럼 조건을 잘 생각하고 적용시켜야겠다..

 

1회독	2회독	3회독	4회독	5회독
V	6/20