[알고리즘] 백준 1978

[문제] : 100 이하의 숫자들 소수 판별하기

[풀이1] : 숫자 N 에 대하여 N-1 까지 일일히 나누기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int count = 0;
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(st.nextToken());
            if(isPrime(n)) count++;
        }
        System.out.println(count);
    }

    static boolean isPrime(int number){
        if(number==1){
            return false;
        }

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

        return true;
    }
}

[풀이2] : 만약 숫자 N 이 공약수를 가지고 있으면 A * B 의 형태일 것이고, 그러면 A, B 중 하나는 Math.sqrt(N) 보다 작을 것이다 라는 것으로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int count = 0;
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(st.nextToken());
            if(isPrime(n)) count++;
        }
        System.out.println(count);
    }

    static boolean isPrime(int number){
        if(number==1){
            return false;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if(number % i == 0) return false;
        }

        return true;
    }
}

[풀이3] : 에레토스테네스의 체 ( 가장 일반적인 방법이다 )

public class Eratosthenes {
    static boolean[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        checkPrime(N);

    }
    static void checkPrime(int N){
        arr = new boolean[N];
        if(N < 2) return;

        // true 면 소수 x, false 면 소수
        arr[0] = arr[1] = true;
        for (int i = 2; i <= Math.sqrt(arr.length); i++) {
            if(arr[i]) continue;

            for (int j = i * i; j < arr.length; j += i) {
                arr[i] = true;
            }
        }
    }
}

참고 : https://st-lab.tistory.com/80