수학 :: 백준 :: 소수 찾기 :: 1978

소수 찾기

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

[문제 풀이]

입력받을 숫자의 개수의 범위는 1 <= N <= 100이고

입력받는 수의 범위는 1000이하의 자연수이다.

소수를 찾는 방법 중에 에라토스테네스의 채 라는 방법이 있다.

예를들어 1부터 20 까지의 수 중 소수를 찾는다고 하면

 - 2부터 검사를 한다.(2가 가장 작은 소수이므로)

   2를 소수라고 체크를 하고, 2의 배수들은 모두 소수가 아니라고 체크를한다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

※※짙은 색이 소수, 옅은색은 소수가 아닌 수

 - 3을 소수라고 체크 한 뒤 3의 배수들은 모두 소수가 아니라고 체크를 한다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

 - 4를 체크해야하는데 이미 소수가 아니므로 5를 체크한다.

 - 그 뒤는 앞의 과정을 반복한다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

연산이 끝난 후 짙은 색으로 칠해져 있는 수들이 소수라는 것을 알 수 있다.(설명을 잘 못해서...ㅠㅠ)

위의 개념을 그대로 들고와 문제 푸는데 적용하면 된다.

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[]str = br.readLine().split(" ");
        int count =0;
        int tmp;
        for(int i=0;i<str.length;i++){
            tmp = Integer.parseInt(str[i]);
            if(tmp == 2) count++;
            else if(tmp != 1) {
                for(int j=2;j<tmp;j++){
                    if(tmp%j==0)break;
                    else if(j == tmp-1)
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

잔뜩 설명하고 나서 코드를 보니,,,, 예전에 풀었던 터라 역시 반복적인 계산을 많이 했다는 것을 알 수 있다.