에라토스테네스의 체

---

/* boolean 배열 이용 */
boolean[] isPrime = new boolean[MAX];
 
// = Arrays.fill(isPrime, true)
for(int i = 2 ; i < MAX ; i++) {
    isPrime[i] = true;
}
 
for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
    for(int j = i * i ; j < MAX ; j += i) {
        if(!isPrime[j]) continue;
        
        isPrime[j] = false;
    }
}
 
 
/* boolean 이용 */
private static boolean isPrime(int num) {
    if(num == 1) return false;
        
    for(int i = 2 ; i <= (int)Math.sqrt(num) ; i++) {
        if(num % i == 0) {
            return false;
        }
    }
 
    return true;
}

 

---

(참고)

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

JAVA [자바] - 소수 구하는 알고리즘 및 구현

[알고리즘] 에라토스테네스의 체(소수 구하는 알고리즘) 자바 구현