숫자가 주어지면 소수인지 아닌지 판별하는 프로그램.

소수판별

function isPrime(n) {
  if (n <= 1) {
    return false;
  }

  // 2부터 n-1까지의 수로 나눈다
  for (let i = 2; i < n; i++) {
    // 자기자신외의 숫자로 나뉘어진다면 소수가 아니다.
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

console.log(isPrime(10));

시간복잡도: O(n)

다른방법.

시간복잡도를 줄일 수 있는 방법.
모든 소수는 6k+-1의 형태를 지닌다.

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;

  // 입력된 수가 2 또는 3인 경우
  // 아래 반복문에서 다섯개의 숫자를 건너 뛸 수 있다.
  if (n % 2 === 0 || n % 3 === 0) return false;

  for (let i = 5; i * i == 0; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }

  return true;
}

console.log(isPrime(97));

시간복잡도: O(sqrt(n))

위의 방법은 정확하게 이해한 것이 아니라 부끄럽지만... 🙄