소수알고리즘 (1) 썸네일형 리스트형 [알고리즘] 소수의 판별 / 투 포인터 / 구간 합 계산 / 순열과 조합 소수의 판별 [특정 숫자 소수 판별] 제곱근 사용. 시간 복잡도 : O(X^1/2) import math def is_prime_number(x): for i in range(2,int(math.sqrt(x))+1): if x%i==0: return False #소수 아님 return True #소수 is_prime_number(숫자) [특정 범위 소수 판별 (에라토스테네스의 체)] 시간 복잡도 : O(NloglogN). 메모리를 많이 필요하기 때문에 N이 1,000,000 이내여야 함 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정.. 이전 1 다음