[Baekjoon] 1978 - 소수 찾기

📝 문제

 

 

🔑 풀이 과정

① 주어지는 수의 개수의 최대값은 100(10^2)

수의 범위의 최대값은1000(10^3)

일반적인 소수판별 방법을 사용 시 최악은 100 * 1000 = 10^5 이므로, 시간제한에 걸리지 않는다.

 

② 수를 하나씩 입력받을 때 마다 소수인지 아닌지를 체크한다.

굳이 배열로 수를 저장하거나 할 필요가 없다.

 

③ 소수인지 아닌지를 마지막에 확인하기 위해 boolean 변수를 사용했다.

boolean이 true면 소수, false면 소수가 아님

 

④ x라는 수의 소수 판별 법

(1) 1이면 소수가 아니므로 boolean 변수 false로 바꿔줌

(2) 1이 아닌경우는, 반복문을 사용해서

2부터 제곱근x까지의 수로 나눠보면서, 나누어지면 소수가 아니므로 boolean 변수 false로 바꿔준뒤 반복문 탈출

(3) 마지막에 boolean 변수가 true면 count를 증가시킴

 

⑤ 수를 하나 입력받을 때 마다, boolean변수를 true로 초기화시킨다.

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    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 N = Integer.parseInt(br.readLine());

        int count = 0;
        boolean isPrimeNumber;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(st.nextToken());

            isPrimeNumber = true;

            if(x == 1){
                isPrimeNumber = false;
            } else{
                for(int j = 2; j <= Math.sqrt(x); j++){
                    if((x % j) == 0){
                        isPrimeNumber = false;
                        break;
                    }
                }
            }

            if(isPrimeNumber)
                count++;

        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

🖤 알고리즘 분류

- 수학

- 정수론

- 소수 판정

- 에라토스테네스의 체