PS-수학

소수

정의 : 1과 자기자신만을 약수로 가지는 수
*1은 소수가 아니다.

소수찾기 > O(n)

for i in range(2,n):
	if (n % i) == 0
    return False
return True

하지만 소수찾기의 연산을 O(루트n)으로 줄일 수 있다.
이유 : 합성수 n에서 1일 제외한 가장 작은 약수는 루트n이하 이다.

증명 :
1. 1을 제외한 가장 작은 약수를 x라고 가정.
2. N/x또한 N의 약수일 것.
3. N의 약수인 두 수 에 대해 1번 가정에 의해 x <= (N/x)
4. x^2 <= N
5. 가장 작은 약수인 x는 최대 루트n의 값을 가진다.

소수찾기 > O(루트n)

i = 2
while (i*i <= n)
	if (n % i) == 0
    return False
	i+=1
return True

파이썬의 for문을 쓰지 않은 이유는 루트n을 직접 쓰지 않기 위함이다.
Float형은 연산이 많아질수록 오차가 생길 수 밖에 없기 때문.

범위 내 소수를 전부 찾는다 할 때...

위의 방식으로도 반복문으로 해도 n = 500만 까지는 1.8초 정도의 시간 밖에 걸리지 않음. (중간에 break)하기 때문.

그러나, 개선의 여지가 많다.

개선1 ::: 그 이전까지의 소수로 나누어 떨어지지 않는다면, 무조건 소수이다.

def fp2(n):
	if n == 1:
		return False
	for j in L:
		if j * j > n:
			return True
		if n % j == 0:
			return False
	return True

>>> 범위 a~b내에 소수 찾을 때, 배열 L에는 a-1 범위까지의 소수가 들어있어야 함. (기존방식)
이러한 방식을 통하면, 500만도 1초 이내로 잡을 수 있다.

이유 :
1. 모든 합성수는 1을 제외한 수로 소인수분해 가능하다.
2. 이유1에서의 소인수란 결국 소수임을 의미한다.
3. 즉 소수로 나누어 떨어졌는지를 살피는 행위는 합성수로 나누어 떨어졌는지 확인하는 행위까지 포함한다.
4. 그래서 j * j < n 범위의 소수 j에 대해 나누어 떨어지지 않는다면 n은 소수가 된다.

최대공약수
연립합동방정식
이항계수