[백준, 자바, 4134번] 다음 소수

풀이

• 해당 문제는 뭔가 좀 아리송했다.
• 이유는 범위가 40억까지라서 int 타입으로는 해결이 불가하다보니
• 처음 고안했던, 가장 큰값을 기준으로 모든 소수를 구한 다음
• 이분 탐색으로 해당 값을 찾는 형식으로 하려고 했는데,
• 계속 시간초과가 발생해서 이유를 뭔가하고 생각해보니
• 중간에 인덱스에 접근하기 위해 int 타입으로 변환한 것 때문에
• 음수로 뭔가 변경되어 발생한 문제가 아닐까하고 생각이 듬... (확실하진 않지만)
• 그래서 그냥 단순히 값을 가져오면 각각의 수에 대한 소수를 판별하고자 함.
• 그리고 int 타입으로 인덱스에 접근 가능하며, 다량의 소수를 판별하고자 할 경우엔
• 에라토스테네스의 체를 생각해내어 해결하면 될 듯하다.
  • 2중 for문을 활용해서 i의 배수가 되는 인덱스 값을 모두 지우는 형식으로 
  • 빠르게 소수를 구분할 수 있는 방법

 

// 해결 코드

import java.io.*;
import java.util.*;
public class _4134 {
    static List<Long> sosu = new ArrayList<>();
    static long mx = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long N = Long.parseLong(br.readLine());

        for (long i=0; i<N; i++) {
            long num = Long.parseLong(br.readLine());
            while (!f_prime(num)) num++;
            bw.write(num+"\n");
        }
        bw.flush();
    }
    public static boolean f_prime(long num) {
        boolean state = true;
        if (num<2) state = false;
        else  {
            for (long j=2; j<=(long)Math.sqrt(num); j++) {
                if (num%j==0) {
                    state = false;
                    break;
                }
            }
        }
        return state;
    }
}

 

// 시간 초과 코드

import java.io.*;
import java.util.*;
public class Main {
    static List<Long> sosu = new ArrayList<>();
    static long mx = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long N = Long.parseLong(br.readLine());
        long[] li = new long[(int)N];

        for (int i=0; i<(int)N; i++) {
            li[i]=Long.parseLong(br.readLine());
            if (li[i]>mx) mx=li[i];
        }
        for (long i=1; i<=mx; i++) {
            boolean state = true;
            for (long j=2; j<=(long)Math.sqrt(i); j++) {
                if (i%j==0) {
                    state = false;
                    break;
                }
            }
            if (state) sosu.add(i);
        }
        for (long num: li) {
            boolean state = false;
            long result = s_find(num);
            if (result==mx&&sosu.get(sosu.size()-1)<result) {
                long val = num+1;
                while (true) {
                    boolean check = true;
                    for (long j=2; j<=(long)Math.sqrt(val); j++) {
                        if (val%j==0) {
                            check = false;
                            break;
                        }
                    }
                    if (check) {
                        bw.write(val+"\n");
                        break;
                    } else val++;
                }
            } else {
                bw.write(result+"\n");
            }
        }
        bw.flush();
    }
 
    public static long s_find(long num) {
        int s=0; 
        int e=sosu.size()-1; 
        int mid; 
        long result = mx;
        while (s<=e) {
            mid = (s+e)/2;
            if (num<=sosu.get(mid)) {
                if (result>=sosu.get(mid)) result = sosu.get(mid);
                e = mid-1;
            } else s = mid+1;
        }
        return result;
    }
}