백준 1978 - 소수 찾기

주어진 N개의 수 중에서 소수가 몇 개인지 찾아서 출력하는 문제이다.

public class Main{
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int size = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int n;
        int counter=0;
        for (int i = 0; i < size; i++) {
            n = Integer.valueOf(input[i]);
            if (isPrime(n)) counter++;
        }
        bw.write(counter+"");
        bw.flush();
        bw.close();

    }
    public static boolean isPrime(int n){
        if(n<=1) return false;
        else if(n>2){
            for(int i=2;i<n;i++) if(n%i ==0)return false;
        }
        return true;
    }
    
}

 

소수를 찾는 여러가지 방법

 

소수 : 1과 자기자신만 약수, n-1보다 작거나 같은 수로 나뉘면 안된다. 

1.정의를 그대로 이용

public static boolean isPrime(int n){
    if(n<2) return false;

    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }

    return true;

 

2. 가장 큰 약수가 n/2인 점을 이용 (n/2+1 ~ n-1 약수가 존재하지 않는다)

- 소수가 되려면 2보다 크거나 같고 N/2보다 작거나 같은 수로 나누어 떨어지면 안된다.

public static boolean isPrime(int n){
    if(n<2) return false;

    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0) return false;
    }

    return true;
}

 

3. 루트 N이용

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

if N이 소수가 아니라면

N = a*b 일때, 한쪽은 루트 N보다 작거나 같고 한쪽은 루트 N보다 커거나 같아야  둘을 곱했을 때, 

N이 나올 것이다. 

따라서 루트 N을 기준으로 이보다 작은 수와 큰 수로 N의 약수를 나눌 수 있다.

N = 18 --> 18의 약수는 1 2 3 6 18 루트 18은 4.xxx이므로 1 2 3 까지만 검사해보면 되는 것이다.

 

public static boolean isPrime(int n){
    if(n<2) return false;

    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) return false;
    }

    return true;
}

--->이것도 가능
 for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }