Algorithm Find a prime

알고리듬 Find a prime을 알아보겠습니다.

​
소수는 1과 자기 자신으로 만 나눠지는 수를 말합니다.
0과 1은 소수가 아닙니다.
​
소수를 구할 때에는 약수의 성질을 이용합니다.





약수의 경우 대칭되는 값이 존재합니다.

따라서, 우리는 소수를 확인하기 위해 1에서 26까지 전부 확인할 필요 없이 1과 2만 확인하면 13, 26을 확인한 것과 똑같습니다.

​

그렇다면, 이 절반을 어떻게 찾을 수 있을까요?

바로 제곱근(root)을 사용합니다.

약수가 저렇게 대칭되지만, 제곱근의 경우 대칭되는 수가 자기 자신이기 때문입니다.

​

26의 경우 대략 5입니다.




따라서, 1~ 5까지만 확인하면 됩니다.

​

​

​

코드로 한 번 봅시다.

1 보다 작으면 False

2와 3이면 True

그 외에는 12번째 줄처럼 math.sqrt를 이용해서 절반까지만 확인하면 됩니다.













끝.



카테고리: Algorithm

댓글

이 블로그의 인기 게시물

음악 총보(Score), 파트보(Part)

딩기 요트 명칭

일본어 문장부호

KiCad 시작하기 3 (새로운 소자 추가하기)

Android Custom IME(Input method editor) 만들기

Python urllib.parse.quote()

Python OpenCV 빈 화면 만들기

KiCad 시작하기 2 (PCB 만들기)

Android GDPR Consent 사용

KiCad 시작하기 1 (회로도 만들기)