Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- SQL
- backpropagation
- A Neural Algorithm of Artistic Style
- Python
- 자전거 여행
- 합성곱 신경망
- 딥러닝
- 역전파
- bayesian
- 냥코 센세
- Autoencoder
- 전처리
- Gram matrix
- 소인수분해
- 히토요시
- 오토인코더
- mnist
- 수달
- c#
- 소수
- 오일러 프로젝트
- CNN
- 역전파법
- 신경망
- project euler
- 비샤몬당
- neural network
- 베이지안
- Convolutional Neural Network
- deep learning
Archives
- Today
- Total
통계, IT, AI
[PROJECT_EULER] 60. Prime pair sets 본문
문제는 이곳에서 확인할 수 있다. 어떤 소수 두개를 앞뒤로 합치면 그 수도 소수가 되는 경우가 있다. 예를 들면, 3과 7, 3과 11 등이 있다. 이를 연결되었다고 하자. 3, 7, 109 그리고 673은 두개의 원소를 뽑았을때 모두 연결되며, 원소의 개수가 4개인 집합 중 합이 가장 작다. 개수가 5인 집합 중 합이 가장 작은 것을 찾고 그 합을 구하는 것이 문제이다.
3부터 시작하여 소수 판별을 한 뒤, 새로 찾은 소수가 기존의 소수와 연결되는지 판단한다. 길이가 3인 집합이 만들기 위해서는, 연결되는 두 소수를 고른 뒤 모든 원소가 새로 찾은 소수와 연결되는 지 확인하면 된다.
예를 들어 새로 찾은 소수가 109라고 하자. 기존의 소수로 만들 수 있는 109와 연결된 소수는 {3, 109}, {7, 109}가 있다. 이제 길이가 2인 집합에서 모든 원소가 109와 연결되는지 확인한다. {3, 7}, {3, 37}, ... , {101, 107}에서 모든 원소가 109와 연결되는 집합은 {3, 7} 뿐이다. 이렇게 길이가 3인 집합 {3, 7, 109}를 만든다. 즉, 길이가 k인 집합을 만들기 위해서는 길이가 k-1인 집합 가운데 모든 원소가 새로 찾은 원소가 연결되는지 확인하면 된다.
import sympy # 소수 판별 함수를 별도로 구현하지 않음
def is_connected(num1, num2):
for x1, x2 in ((num1, num2), (num2, num1)):
x = str(x1) + str(x2)
x = int(x)
if not sympy.isprime(x):
return False
return True
prime_cand = 1
prime_list = []
target_pair_set_len = 5
connected = {k: [] for k in range(2, target_pair_set_len + 1)}
while True:
prime_cand += 2
if str(prime_cand)[-1] == '5':
continue
if not is_prime(prime_cand):
continue
con2_found = []
for p in prime_list:
if is_connected(p, prime_cand):
connected[2].append((p, prime_cand))
con2_found.append((p, prime_cand)) # 이 부분이 거슬리지만 속도를 위해 추가하였다.
for coef in range(2, target_pair_set_len):
for pair_set_found in connected[coef]:
satisfied = 0
for p in pair_set_found:
if not (p, prime_cand) in con2_found:
break
else:
satisfied += 1
if satisfied == coef:
upper_pair_set = list(pair_set_found) + [prime_cand]
upper_pair_set = tuple(upper_pair_set)
connected[coef+1].append(upper_pair_set)
prime_list.append(prime_cand)
if len(connected[target_pair_set_len]) == 1:
break
ans_pair_set = connected[target_pair_set_len]
print(ans_pair_set[0])
print(sum(ans_pair_set[0]))
길이가 5인 집합 중 합이 가장 작은 것은 {13, 5197, 5701, 6733, 8389}이며, 답은 26033이다.
'IT > PROJECT_EULER' 카테고리의 다른 글
[PROJECT_EULER] 62. Cubic permutations (0) | 2023.03.22 |
---|---|
[PROJECT_EULER] 61. Cyclical figurate numbers (0) | 2023.03.21 |
[Proejct Euler] 59. XOR decryption (0) | 2017.07.29 |
[Project Euler] 58. Spiral primes (0) | 2017.07.27 |
[Project Euler] 57. Square root convergents (0) | 2017.07.26 |
Comments