백준 4948 베르트랑 공준

시간 복잡도를 신경 안썼더니 점점더 시간이 오래걸린다. 10000을 입력하고 시간을 재보니 2초정도 나왔다. 너무 오래걸린다.

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr=new ArrayList<Integer>();
        int input;
        int min,max;
        int count=0;
        while(true){
            input=scanner.nextInt();
            if(input==0)
                break;
            else
                arr.add(input);
        }
        for(int i=0;i<arr.size();i++){

            min=arr.get(i);
            max=2*arr.get(i);
            for(int j=min;j<=max;j++){
                if(j==1)
                    continue;
                else if(j==2)
                    count++;
                else {
                    for (int z = 2; z < j; z++) {
                        if (j % z == 0)
                            break;
                        if ( z==j - 1) {
                            count++;
                        }
                    }
                }
            }
            count=0;
        }
    }
}