공부하자

소수(Prime Number)란? 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수 소수를 판별하는 데는 2가지 방법이 있다. 특정 수 N이 소수인지 알기위해, 2부터 N-1까지의 수로 N을 나눠보고, 어떤 수로도 나눠 떨어지지 않는 다면 N은 소수. 에라토스테네스의 체를 이용하는 방법 1. 2부터 n-1까지의 수로 n을 나눠보기 첫번째 방법을 코드로 나타내면 다음과 같다. def isPrime(n): for i in range(2, n): if n % i == 0: return False return True 이 코드는 2부터 n-1까지 모든 숫자를 확인하며 소수인지 판별하는 방법이기 때문에 시간 복잡도가 O(n)이 나온다. 숫자가 커질수록 오래걸린다. 여기서 약수의 특성인 대칭성을 사용하면 연..