📙

소수 판별 알고리즘

직접 나누어서 계산하기

function isPrime(num) {
  if(num === 2) return true;

  for(let i = 2; i < num; i++){
    if(num % i === 0) return false;
  }
  return true;
}
JavaScript
복사

시간복잡도는 O(n)

N / 2 까지만 나누어서 계산하기

function isPrime(num) {
  if(num === 2) return true;

  for(let i = 2; i<=num/2; i++){
    if(num % i === 0) return false;
  }
  return true;
}
JavaScript
복사

시간복잡도는 O(n)

제곱근 이용하기

function isPrime(num){
  if(num % 2 === 0 || num === 1) return false;
  for(let i = 3; i<= num ** (1 / 2); i += 2){
    if(num % i === 0) return false;
  } 
  return true;
}
JavaScript
복사

시간복잡도는 O(

\sqrt{n}

)

에라토스테네스의 체

function isPrime(num) {
    // it gets all prime numbers from 2 to n
    let sieve = new Array(n+1).fill(true);

    sieve[0] = false;
    sieve[1] = false;
    
    for(let i = 2; i * i <= num; i++){
        if(sieve[i]){
          // j=i*i를 해도 무관하지만,
          // 범위가 100만인 경우에는 i*i가 1조가 되어 숫자의 범위를 초과할 수 있다.
          for(let j = i + i; j <= num; j += i){
              sieve[j] = false;
          }
        }
    }

    return sieve.reduce((acc, cur, idx) => cur ? acc.concat(idx) : acc, []);
}
JavaScript
복사