백준 1978번 소수찾기

주어진 N개의 숫자중 소수(Prime Number)를 가려내는 알고리즘을 만들어야 한다.

소수는 1과 자기 자신으로만 나누어져야 하는 숫자 이기에, 단순하게 생각한다면 각 수에 대해서 2부터 자기 자신까지 나누어 보면 해결되는 문제이다. 하지만 시간복잡도가 O(N)으로 비효율적이다.

public class Main{
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i<num; i++){
            if(num%i==0) return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        int ans = 0;
        for(int i=0; i<t; i++){
            int a = sc.nextInt();
            if(isPrime(a)) ans++;
        }
        System.out.println(ans);
    }
}

다른 방안을 채택해야한다.

제곱근을 이용하는 방식이다.

판별을 해야 하는 N이 A X B의 합성수라고 가정할때, 1 ≤ A, B < N 이고 따라서

A, B > sqrt(N) 이다.

결국 A혹은 B는 sqrt(N)보다 작거나 같아야 한다.

2부터 자기 자신까지 대조해보며 나누기보다 주어진 수의 제곱근까지만 나누어 보면 되서 더욱 효율적이다.

public class Main{
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i==0) return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        int ans = 0;
        for(int i=0; i<t; i++){
            int a = sc.nextInt();
            if(isPrime(a)) ans++;
        }
        System.out.println(ans);
    }
}