[JAVA] 백준 4134 다음 소수

4134번: 다음 소수 (acmicpc.net)

4134번: 다음 소수

 

풀이 과정 

 

- 소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없음

- 검사할 데이터를 제곱근 개 이하로 줄일 수 있는 방법 

 

2024.01.28 - [Java/자료구조] - 2-1 배열

2-1 배열

 

정답

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    //a 이상의 소수 중 최솟값 구하기 
    public static boolean isPrime(long n)
    {
    	//소수 판별시 루트 n까지 나누어 진행 
    	if(n<2)
    	{
    		return false;
    	}
    	
    	for(int i=2; i<=Math.sqrt(n); i++)
    	{
    		if(n%i==0) return false; //나누어지면 소수가 아님
    	}
    	return true;
    	
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int num = Integer.parseInt(br.readLine());
        
        for(int i=0; i<num; i++)
        {
            long n = Long.parseLong(br.readLine());
            
            if(n<=2) 
            {
            	bw.write(2+"");
            }
            else
            {
            	while(!isPrime(n))
            	{
            		n++;
            	}
            	bw.write(n+"");
            }
            bw.newLine();
          
        }
   
        bw.flush();
        bw.close();
        
    }
}