[백준][1978번] 소수찾기

문제 URL

https://www.acmicpc.net/status?user_id=hscom96&problem_id=1978&from_mine=1

나의 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] num = new int[size];
        int answer =0;

        for(int i=0; i<size; i++)
            num[i] = Integer.parseInt(str[i]);

        for(int i=0; i<size; i++){
            if(is_prime(num[i])){
                answer++;
            }
        }

        System.out.println(answer);
    }

    public static boolean is_prime(int x){
        if(x<=1)
            return false;
        else if(x==2)
            return true;
        for(int j=2; j*j <= x ; j++){
            if( (x % j) == 0) {
                return false;
            }
        }
        return true;
    }
}

느낀점

소수 구하기 문제다.

소수란 약수가 1과 자기자신 밖에 없는 수이다.

N이 소수가 되려면 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

이유는 N이 소수가 아니라면 N = a*b로 나타낼수있다. (a<=b)
a>b라면 두 수를 바꿔서 항상 a<=b로 만들수있다. 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

따라서 루트 N까지만 검사를 해보면된다.