[알고리즘] 소수 판별 구현 (Java)

프로그래머스를 이용해서 코딩테스트를 하다가 굉장히 좋은 효율의 소수 판별 isPrime()을 구현한 것을 발견하고,

내 나름대로의 의견을 추가하고 수정해서 정리해두려한다.

 

우선 아래의 코드를 조금 더 쉽게 이해하기 위해 두 가지를 알면 좋다.!

1. 2를 제외한 나머지 짝수들은 모두 소수가 아니다. 

2. n(숫자)가 소수인지 확인하기 위해 √n 보다 큰 수를 나눠보는 것은 무의미한 일이다.

왜냐면 n이 √n 보다 큰 수로 나눠진다는 것은 몫으로 √n 보다 작은 수가 나온다는 말인데,

그러면 √n 보다 큰 수로 나눠떨어지기 전에 이미 소수가 아님을 발견 할 수 있게 된다. -> "유레카!"

 

이를 이해하고 나서 해당 코드를 함께 보자.

    if(a==2) count++;
    if(a%2!=0 && isPrime(a)){
        count++;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

isPrime() 함수를 호출하기 전에 짝수라면 isPrime() 함수를 호출조차 하지 않는다!

그리고 isPrime의 for 문을 보게되면 √n보다 작거나 같을 동안만 for 문이 돌아간다!

그리고 인덱스 값을 3부터 시작하고 2씩 증가한다!

(짝수는 2와 2가 아닌 수를 isPrime() 호출 전에 판별 하였기에 짝수로 나눌 이유가 없기 때문)

 

해당 코드에서는 2를 소수로 판별하고 2로 나눠 떨어지는 것을 소수가 아닌 것으로 판별하는 것과

isPrime() 함수를 분리 하였는데,

 

나였으면 2를 소수로 판별하는 것과 2로 나눠 떨어지는 것이 소수가 아닌 것으로 판별하는 것도 isPrime() 이 해야한다고 생각한다...(선넘기 시작) 이는 지극히 헛다리 고수의 주관적인 의견이다.(코딩 고수 아님 주의)

 

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        if(n == 2) return true;
        if(n % 2 == 0) return false;
        
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

그리하여 나만의 isPrime은 이러하다!

 

만약 나의 코드가 잘못되었다면 불쌍한 헛다리 장인에게 조언을 해주기 바란다...

물어볼 사람이 없어서 처음보는 당신에게 조언을 바랄 수 밖에 없다...

 

끝!

 

---

출처

programmers.co.kr/

프로그래머스