수학 알고리즘 - 소수 판별 알고리즘(브루트 포스, sqrt, 에라토스테네스의 체)

소수란

소수는 1과 자기 자신으로만 나누어지는 양의 정수입니다.

예를 들어 2, 3, 5, 7, 11등이 있습니다.

 

브루트 포스를 이용한 소수 판별(n -1까지) 코드 예시

function isPrime(num) {
 for(let i = 2; i < num; i++) {
  if(num % i === 0) return false
 }
 return true
}

2부터 시작하여 num - 1까지 나머지를 검사하면서 0이 있으면 소수가 아니고 나머지가 0이 하나라도 없으면 소수입니다.

 

브루트 포스를 이용한 소수 판별(sqrt 까지) 코드 예시

function isPrime(num) {
 for(let i = 2; i <= Math.sqrt(num); i++) {
  if(num % i === 0) return false
 }
 return true
}

num = n * n입니다. 뒤에 있는 n이 작아지면 앞에 있는 n은 커집니다. n * n을 까지만 검사하면 나머지는 앞에서도 검사한 부분이라서 sqrt까지만 검사해도 됩니다.

 

브루트 포스를 이용한 소수 판별(짝수제외한 sqrt 까지) 코드 예시

function isPrime(num) {
 if(num % 2 === 0 && num !== 2) return false
 for(let i = 3; i <= Math.sqrt(num); i+= 2) {
  if(num % i === 0) return false
 }
 return true
}

2를 제외한 짝수는 소수가 아니라서 3부터 홀수만 검사하는 로직입니다.

 

에라토스테네스의 체 개요

특정 정수 이하의 모든 소수를 찾기 위해서 소수를 직접 찾는게 아니라 반대인 합성수를 식별 후 제외하는 방법입니다.

 

에라토스테네스의 체 동작원리

N 정수까지의 모든 소수를 구할 때 N + 1의 배열을 만들어줍니다.(인덱스는 0부터 시작)

sqrt(n)까지 2..3..4..5..7..의 배수들을 만든 배열에서 true로 만들어줍니다.

false일 때만 배수 검사를 실시합니다.

검사가 끝나고 true인 인덱스만 출력합니다.

 

에라토스테네스의 체 코드 예시

function eratos(num) {
 const eratosArray = new Array(num +1).fill(false)
 eratosArray[0] = false
 eratosArray[1] = false
 for(let i = 2; i <= Math.sqrt(num); i++) {
  if(eratosArray[i]) {
   for(let j = i * j; j <= num; j+=i) {
    eratosArray[j] = true
   }
  }
 }
 
 const primaArray = new Array()
 eratosArray.forEach((e, idx) => {
  if(e) primaArray.push(idx)
 })
 
 return primaArray
}