crew   1년 전

이클립스에서 따온건데요. 이게 빠르다는데 어떻게 돌아가는지 설명해주실 수 있나요.

candidate로 들어온 수를 소수인지 아닌지 boolean으로 처리합니다.

hdnua   1년 전

(candidate & 1)은 가장 첫 자리 비트가 1인지, 즉 인자가 홀수인지 짝수인지를 판별합니다. 2라면 참, 아니면 거짓입니다.

반복문은 3부터 시작하여 root(candidate) 이하의 모든 홀수가 인자의 인수인지 판별합니다. 하나라도 인수라면 거짓입니다.

마지막으로 인자가 1인지 아닌지를 판별합니다. 1이라면 거짓, 그 외에는 모두 참입니다.


학교 과제에서나 볼 법한 소수 찾기 코드로, 속도는 일반적입니다.

함수 호출시마다 매번 소수인지 판별하기 때문에, 자주 호출되어야 한다면 에라토스테네스의 체를 사용하는 것이 바람직하다고 생각합니다.

jnk98   1년 전

참고로 위의 알고리즘은 짝수만 제외하고 검사를 하도록 되어있는데, 6n+1, 6n+5 꼴만 검사하도록 수정하면 수행시간을 2/3로 단축 가능 합니다.

6n+3 꼴은 3의 배수이므로 제외 시키겠다는 거죠..

댓글을 작성하려면 로그인해야 합니다.