소수 판별 알고리즘(JAVA)

 

소수

 1과 자기 자신을 제외한 자연수들을 약수로 갖고 있지 않은 수이다. (ex : 2, 3, 5, 7 ...)

 

제곱근을 이용한 방식

    public boolean isPrime(long num) {
        if (num == 1)  {
            return false;
        }

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

        return true;
    }

 

에라토스테네스의 체를 이용한 방식

import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(st.nextToken());

        int result = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            boolean[] prime = new boolean[num + 1];
            isPrime(num, prime);

            if (prime[num]) {
                result++;
            }
        }

        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static boolean[] isPrime(int num, boolean[] prime) {

        Arrays.fill(prime, true);

        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (prime[i]) {
                for (int j = i * i; j <= num; j+= i) {
                    prime[j] = false;
                }
            }
        }

        return prime;
    }
}