이게뭐야?
위키피디아
쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다.
파이썬 구현
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
n = n + 1 # 이렇게 하면 소수목록에서 조회할때 -1 안해줘도 된다
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i]: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return sieve
어따씀?
사전지식 약수 12와 28의 약수는 ? 12의 약수 => 1 2 3 4 6 12 28의 약수 => 1 2 4 7 14 28 서로소 공약수가 1밖에 없는 두수를 서로소 관계에 있다고 한다. 예를들어, 17과 8은 서로소 관계에 있다. 공약수가 1밖에 없기 때문이다. 최대공약수 두 수의 공약수중 가장 큰것. 12와 28의 최대공약수는 4이다. 2와 4둘중에 4가 더 크기 때문이다. 최대공약수 구하는 방법 첫번째(노가다) 12의 약수와 28의 약수를 구한다음에 공통된것을 찾고(공약수), 그중에 가장 큰것(최대공약수)을 찾으면 된다. 직관적이지만, 유클리드 호제법보다 속도가 느리다는 단점이 있다. 두번째(유클리드호제법) 유클리드 호제법이란? A, B의 최대공약수를 G라고 할때(A > B)[28과 12의...
첫번째 방법 import time n = 100000000 factors = [] s = time.time() for i in range(1, n+1) : if n%i == 0 : factors.append(0) print('소요시간 : ', time.time() - s) 소요시간 : 6.5초 두번째 방법 (예를들어) 12의 약수 [1, 2, 3, 4, 6, 12] 중 자신을 제외하고 가장 큰 약수는 12의 절반인 6이니까, 6까지만 12를 1~6으로 나누었을때 나머지가 0인지를 확인해보면 된다. 7~11은 어차피 약수가 아니니까 안나눠봐도 된다는 소리다. import time n = 100000000 factors = [] s = time.time() for i in range(1, n//2 +1) :...