소수 판별 알고리즘 : 에라토스테네스의 체

📍 에라토스테네스의 체를 이용한 소수 구하는 알고리즘

• 소수 구하는 대표적인 방법 중 하나
• k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킴
• 알고리즘의 시간복잡도는 O(N√N)

static boolean isPrime(int val) {

    if(val < 2) return false;
    if(val == 2) return true;

	// 에라토스테네스의 체 : Math.sqrt()
    for(int i = 2; i <= Math.sqrt(val); i++)
        if(val % i == 0) return false;

    return true;
}