[코테 알고리즘] 소수(Prime Number)와 에라토스테네스의 체

소수(Prime Number)

---

1과 자기자신 이외의 약수를 가지지 않는 1보다 큰 자연수를 말한다.

소수(Prime Number) 판별 알고리즘 에라토스테네스의 체

---

특정 수의 제곱근까지만 약수의 여부를 검증하면 된다.

import java.util.*;

class Main {
  public static void main(String[] args) {
    System.out.println(isPrime(97));
  }

  public static boolean isPrime(int num) {
    int end = (int)Math.sqrt(num);
    for(int i = 2; i <= end; i++) {
      if(num % i == 0) return false;
    }
    return true;
  }
}