[백준 1987, Java] 소수찾기

문제

www.acmicpc.net/problem/1978

1978번: 소수 찾기

check

1. 소수의 정의를 이용하여 3가지로 풀 수 있다.

2.  isPrimeNum3에서 두번째 for문에 n<sqrt(num)이 아닌 n*n < num 으로 한 이유는 sqrt(num)은 실수연산(근사값)이 되기 때문에 정수연산으로 바꿔주는게 좋다고 한다. (a<b -> a제곱 < b제곱) 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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));
        StringTokenizer st;
        int primeNumberCount = 0 ;

        int N = Integer.parseInt(br.readLine().trim());
        st = new StringTokenizer(br.readLine()," ");
        for(int n = 0 ; n<N; n++){
            int num = Integer.parseInt(st.nextToken());
            if(isPrimeNum3(num)) ++primeNumberCount;
        }
        bw.write(String.valueOf(primeNumberCount));
        bw.flush();

        br.close();
        bw.close();


    }
    public static boolean isPrimeNum1(int num){
        //소수의 정의 이용 : 1과 자기 자신으로만 나누어 떨어지는 수
        // 따라서 2부터 num-1까지 수 중에서 나누어 떨어지는 경우가 있으면 소수가 아니다
        if(num == 1){
            return false;
        }
        for(int n = 2; n<num; n++){
            if(num%n ==0){
                return false;
            }
        }
        return true;
    }
    public static boolean isPrimeNum2(int num){
        //num이 소수가 아닌 경우 소인수 분해 시 2*(num/2)로 나타낼 수 있다.
        //따라서 2부터 최대 값이 N/2로
        if(num<2){
            return false;
        }
        for(int n = 2; n <= num/2 ; n++){
            if(num%n==0){
                return false;
            }
        }
        return true;
    }

    public static boolean isPrimeNum3(int num){
        //num이 소수가 아니라면 a*b(a<=b) 로 나타냈을 때 a의 최대값은 루트 num 이고 b 의 최댓값은 루트 n이다
        if(num < 2){
            return false;
        }
        for(int n = 2; n*n<=num ; n++){
            if (num%n ==0){
                return false;
            }
        }
        return true;
    }
}