Algorithm - 소수 판단

주어진 숫자 n이 소수인지 판단하는 함수를 만들어보자.

 

방법 1

 

단순하게 숫자 2부터 n - 1 까지 모든 숫자를 하나씩 나누어봤을때 나누어 떨어지면 소수가 아니라고 판단하는 방법이 있다.

 

이 방법은 단순하고 직관적이나 효율적이지 못하다. 왜냐하면, 2를 제외한 짝수는 모두 소수가 아니고, 모든 수는 제곱근의 제곱으로 나타낼 수 있기 때문에 n - 1까지 모두 나누어 볼 필요없이 n 제곱근 이하의 숫자만으로도 소수 판별이 가능하기 때문이다.

 

방법 2 

 

숫자 2부터 n - 1의 제곱근까지 수 중, 홀수 숫자만으로 나누어서 소수 판별.

 

자바

public boolean isPrime(long number) {

    if (number == 1) 
    	return false;

    if (number == 2 || number == 3)
        return true;

    if (number % 2 == 0) return false;

    for (int div = 3 ; div <= Math.sqrt(number) ; div += 2) {
        if (number % div == 0) return false;
    }

    return true;
}

 

자바스크립트

const isPrime = number => {

    if (number == 1) 
        return false;

    if (number == 2 || number == 3) 
        return true;

    for (let i = 3 ; i <= Math.sqrt(number) ; i += 2) {
        if (number % i == 0) return false;
    }

    return true;
}