[백준] 4948번 베르트랑 공준 feat.자바 시간초과

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

4948번: 베르트랑 공준

 

• 풀이

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

public class back_4948 { // 베르트랑 공준
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            int temp = Integer.parseInt(br.readLine());
            if(temp == 0){
              break;
            } else{
                System.out.println(findPrimeNumber(temp+1,temp*2+1));
            }
        }
    }

    private static int findPrimeNumber(int a, int b) {
        int check = 0;
        for(int i=a; i<b; i++){
            if(isPrime(i)){
                check ++;
            }
        }
        return check;
    }

    private static boolean isPrime(int number) {
        for(int i=2; i<=Math.sqrt(number); i++){
            if(number%i == 0){
                return false;
            }
        }
            return true;
    }
}

 

처음에 풀었을땐 하나하나 검사하는 방법으로 해서..ㅎ 시간초과가 났다. 

1. Math.sqrt 사용

2. 나누어지는 순간 소수가 아니니 제외

이렇게 해서 통과했다. 

 

▼아래는 틀린풀이

(너무 직관적으로 풀어서 문제다)

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

public class Main { // 베르트랑 공준
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            int temp = Integer.parseInt(br.readLine());
            if(temp == 0){
              break;
            } else{
                System.out.println(findPrimeNumber(temp+1,temp*2+1));
            }
        }
    }

    private static int findPrimeNumber(int a, int b) {
        int check = 0;
        for(int i=a; i<b; i++){
            if(isItPrime(i)){
                check ++;
            }
        }
        return check;
    }

    private static boolean isItPrime(int i) {
        int cnt = 0;
        for(int j=1; j<i; j++){
            if(i%j == 0){
                cnt ++;
            }
        }
        if(cnt == 1){
            return true;
        } else{
            return false;
        }
    }
}