O(1) 시간 안에 소수 판별하기

 

제목에 낚였다면 미안합니다.

 

최근 레딧과 트위터가 O(1) 시간 안에 소수를 판별하는 함수를 구현했다는 트롤로 떠들썩했다.

한 줄짜리 아주 간단한 함수인데, 항상 입력된 정수가 소수가 아니라고 반환한다.

모든 경우에 소수가 아니라고 하니 완전히 틀린 구현이잖아! 라고 생각할 수 있다.

그런데 정말 그럴까?

 

어떤 수가 커질수록 소수일 확률은 작아진다. 실제로 Prime Number Theorem에 따르면 어떤 수보다 작은 소수의 개수는 n / log n 으로 근사할 수 있다.

그렇다면 이 함수의 정확도는 100 - ((n / log n) / n) * 100 = 100 - (100 / log n) 가 되는데. n이 커짐에 따라 정확도가 100으로 수렴한다 (...) 이것이 의미하는 것은 테스트셋이 커질수록 이 함수는 성능을 잃지 않으면서도 더 정확해진다는 말이다!

 

물론 수학적으로 의미가 있는 함수는 아니다.

 

우리가 프로그램을 작성할 때 항상 정확한 결과를 내어야만 하는 것은 아니다.

적당히 좋은 값을 내는 것이 시스템 전체적으로 더 나은 때가 있다.

데드락을 판단하는 경우를 대표적인 예로 들 수 있을 것 같다.

데드락을 판단하는 알고리즘은 계산 코스트가 아주 비싸다.

그래서 대부분의 운영체제들은 데드락 상태를 판단하지 않는다.

대부분의 경우에 데드락은 발생하지 않기 때문에, 항상 데드락에 걸렸는지 판단하는 건 시스템 자원의 낭비가 심하기 때문이다.

그냥 데드락이 발생하면, 타임아웃을 걸어서 프로세스를 죽이거나 프로그래머가 알아서 대비하도록 하는 것이 낫다.

 

우리가 사용하는 모바일 앱의 경우에도, 네트워크 오류라던가 서버와 클라이언트 사이에 동기화가 실패하는 것처럼 시스템이 오작동하는 경우가 있다. 이럴 때는 프로세스를 종료시켜버리고 유저에게 처음부터 다시 시작하도록 하는 전략을 사용할 수 있다.

시스템이 오작동하는 케이스에 대비하도록 프로그램을 작성하는 것보다 그냥 껐다가 키는 게 더 효율적이기 때문이다.

또는 오작동의 원인을 파악하지 못했는데 서비스를 운영해야만 하는 상황에도 사용할 수 있다. 추후 로깅을 통해 원인을 파악하며 서비스를 업데이트하면 된다.

 

더 큰 그림을 보면, 이 트롤이 정말 완전히 틀려먹은 함수는 아니다.

대부분의 경우에, 빠르게 작동하는 프로그램. 엔지니어라면 마다할 이유가 없다!

 

 

참고

 

Hi!, i have invented O(1) algorithm for checking if number is prime that works in 95%+ cases. For more details checkout comments for link to the github repo : ProgrammerHumor (reddit.com)