[백준] 4134번 다음 소수 JAVA (자바) 풀이

문제 4134 (수학, 브루트포스)

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성

 

 

 [입력]

 

 :  첫째 줄에 테스트 케이스의 개수

 

 :  정수 n ( 각 테스트 케이스는 한 줄 )   

 

 

 

 [출력]

 :  n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력

 

 

 [참고]

 

 소수 찾기 공식

 

• 2 ~ 제곱근까지 입력받은 수로 나눴을 때 나누어 떨어지지 않아야 소수!
• 나누어 떨어진다면 입력받은 수에서 +1씩 올려 계산해보기

 

런타임 에러 피하기

1. 입력받은 숫자 n의 범위가 크기 때문에 long 타입으로 바꿔줄 것!

 

 

[코드]

 

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for(int i =0; i< T; i++){
            long N = Long.parseLong(br.readLine());
            if (N <= 1) N = 2;  
            while(true){
                int count = 0;
                for(int j = 2; j<=Math.sqrt(N); j++){
                    if(N%j==0){
                        count++;
                        break;
                    }
                }
                
                if(count == 0){
                    System.out.println(N);
                    break;
                }
            N++;
            }
        }
    }
}

 

 

 [해설]
     

 :  int T = Integer.parseInt(br.readLine());  테스트 케이스수
       

 :  for(int i =0; i< T; i++){  
            long N = Long.parseLong(br.readLine());  입력받은 정수
            if (N <= 1) N = 2;  1보다 작거나 음수일 경우엔 젤 작은 소수 2뿐이다
            while(true){  반복문 시작
                int count = 0;  
                for(int j = 2; j<=Math.sqrt(N); j++){  제곱근까지 반복
                    if(N%j==0){  입력받은 수 나눴을 때 나누어 떨어지면 소수 아니다
                        count++;  카운트
                        break;  즉각 종료
                    }
                }
                
                if(count == 0){  카운트 0이라면 소수!
                    System.out.println(N);
                    break;  즉각 종료
                }
                N++;  정수 증가시켜 한 번 더 반복
            }
    }
    

    
   

 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

https://www.acmicpc.net/problem/4134