prime number (1) 썸네일형 리스트형 [BOJ] - 기본 수학 2 - 소수 - (1) - Python 소수(Prime number)는 1과 자신의 숫자 이외에 나눠질 수 없는 숫자를 말합니다. 소수를 찾는 함수를 만드는 방법에는 두 가지가 있었습니다. (제가 풀었던 방법 내에서 말씀드립니다.) - 소수가 n이면 2부터 n-1까지 나눠서 한번이라도 나누어떨어지면 소수가 아님을 반환 - 소수가 n이면 2부터 sqrt(n) 전까지 나눠서 한번이라도 나누어떨어지면 소수가 아님을 반환 첫번째 방법은 O(n) 시간만큼 걸리고 두번째 방법은 O(n^0.5) 시간만큼 걸린다고 합니다. 당연히 덜 나누는게 더 빠르겠죠? 두번째 방법은 에라토스테네스 체 알고리즘 내용입니다. 8의 경우 약수는 1, 2, 4, 8 이므로 sqrt(8) = 약 2.8로 1, 2 까지만 나눠도 됩니다. 4와 8은 이미 2에서 나눴으니까요. 이렇.. 이전 1 다음