# '친절한 수론 길라잡이' 12장 89쪽: 3 (mod 4)가 되는 소수 연달아 구하기
# 첫 집합 {7} : A = 4 * 7 + 3 = 31
# {7, 31} : A = 4 * 7 * 31 + 3 = 871 (13*67)
# {7, 31, 67}
# {7, 31, 67, 19}
# {7, 31, 67, 19, 179}
def isPrime(num):
if num <= 1:
return False
root_val = round(num ** 0.5) # 제곱근 값을 구한다
for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
if num % i == 0: # 중간에 나눠지면 소수가 아니다
return False
return True
# 소인수분해하여 그 목록을 돌려준다
# 가령 소인수분해 결과가 2^3*3^2*7 이라면,
# [2, 3, 7]을 돌려준다
def factorize_list(num):
divisor_primes = [] # 분해된 인수를 차곡차곡 저장하는 리스트
if isPrime(num): # 소수 판정
return divisor_primes
# 인수분해 루틴은 소수 판정 루틴과는 조금 다르게 접근할 필요가 있다.
i = 2
while True:
# i가 소수인지 검사해서 소수라면 num을 i로 나눈다
# i로 나눠서 나머지가 0이라면, 인수분해가 한번 된 것이다.
if isPrime(i) and num % i == 0:
divisor_primes.append(i) # 나누는 수를 저장 (가령, num이 12라면 i = 2)
num = num // i # 몫, 가령 24//2 = 12
#print(f"{i}, {num}")
# 12는 소수가 아니므로 반복문 계속. 소수가 나오면 그 소수를 저장하고 반복문 종료.
if isPrime(num):
divisor_primes.append(num)
break # return divisor_primes
i = 2 # 인수분해를 한번 했으므로 숫자를 2로 다시 나눠보기로 설정
else:
i += 1 # 인수분해가 되지 않으면 젯수(나누는 수)를 1증가
return sorted(set(divisor_primes)) # 중복 제거, 정렬하여 돌려주기
# 리스트에 든 숫자들을 모두 곱해서 결과를 돌려준다.
def multi(numbers):
gop = 1
for number in numbers:
gop *= number
return gop
# 연습문제 12.1 풀이와 다른 점은 (함수는 동일하고) 밑에 변수값 3개가 다르고, for 문 내의 if 문에서
# d % m == r 인점을 체크한다는 점
primes = [7] # 찾아낸 소수들을 담는 리스트
m = 4
r = 3
while True:
new_num = multi(primes) * m + r # 3 (mod 4) 만들기
if isPrime(new_num): # 소수라면 소수 목록에 추가
primes.append(new_num)
else: # 합성수라면 소인수분해한다.
divisors = factorize_list(new_num)
found = False
for d in divisors: # 예: [2, 3, 7]
if d % m == r and d not in primes: # 소수 목록에 없는 소수를 찾았다면, 목록에 추가
primes.append(d)
found = True # 찾았음을 표시
break
# 만일 해당 소수가 이미 목록에 있다면 인수분해된 소수 중 다음 소수를 for 문으로 시도한다.
if found == False: # 본인도 소수가 아니고 인수분해된 소수들이 이미 소수 목록에 들어 있다면 포기한다.
print("소수를 찾을 수 없습니다.")
exit(1)
print(primes)
if len(primes) == 7: break # 더 이상 진척이 안 됨
'''
# 실행 결과
[7, 31]
[7, 31, 67]
[7, 31, 67, 19]
[7, 31, 67, 19, 179]
[7, 31, 67, 19, 179, 197788559]
[7, 31, 67, 19, 179, 197788559, 39120313477930807]
'''
# 89쪽, p = 1 (mod 5), p = 2 (mod 5) ... 소수를 찾아보기
def getPrimes_mod_rm(r, m): # p = 1 (mod 5) ==> (1, 5)
for i in range(r, 1000000000000000, m):
if i <= 1: continue
if isPrime(i):
print(i, end=" ")
getPrimes_mod_rm(3, 5)
# 연습문제 12.2.a, b
getPrimes_mod_rm(5, 6)
getPrimes_mod_rm(4, 5)
# 연습문제 12.6a, b
# gcd(1338, 1115) = 223 이어서 만족하는 소수를 찾을 수 없음
getPrimes_mod_rm(1338, 1115)
# gcd(1438, 1115) = 1 이어서 만족하는 소수가 무수히 많음
getPrimes_mod_rm(1438, 1115)카테고리 없음