[Algorithm] 특정값 소수 판별하기

1번. (전부 비교)

시간 복잡도 : O(N)

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i<num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

2번. (절반까지 비교)

시간 복잡도 : O(N)

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i<=num/2; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

3번. (√N까지 비교)

시간 복잡도 : O(√N)

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}