subject

describe

Title Description
If the sum of two positive integers is prime, the two positive integers are called "prime partners", such as 2 and 5, 6 and 13, which can be applied to communication encryption. Now the society of cryptography asks you to design a program to select several pairs from the existing N (N is an even number) positive integers to form a "prime partner". There are various selection schemes. For example, there are four positive integers: 2, 5, 6 and 13. If you divide 5 and 6 into a group, you can only get one group of "prime partners", while grouping 2 and 5, 6 and 13 will get two groups of "prime partners", The scheme that can form the most "prime partners" is called the "best scheme". Of course, the cryptography society hopes you to find the "best scheme".

Input:

There is a positive even number N (N ≤ 100), which represents the number of natural numbers to be selected. Specific figures are given later, ranging from [230000].

Output:

Output an integer K, indicating the logarithm of the "prime partner" composed of the "best solution" you obtained.

Enter Description:

Enter description
one   Enter a positive even number n
two   Enter n integers
Note: there may be multiple groups of data

Output Description:

The "best plan" obtained constitutes the logarithm of the "prime partner".

Input:

```4
2 5 6 13
2
3 6
```

Output:

```2
0
```

Problem solving ideas

(1) Even numbers plus even numbers have a common factor of 2, so even numbers and even numbers must not be prime numbers

(2) First, divide the input numbers into parity

```def group_lst(lst): ##Partial parity
a, b = [], []
for i in lst:
if int(i) % 2 == 0:
a.append(int(i))
else:
b.append(int(i))
return a, b```

(2) Judge whether it is a prime number: HJ6 prime factor

```def prime_judge(n):
m = int(n ** 0.5) + 2
for i in range(3, m, 2):
if n % i == 0:
return False
return True```

(3) Construct a matrix l record, record the result of odd and even pairwise addition, mark the result with prime number as 1, and the rest as 0

```def matrix_ab(a, b):
l = [[0 for _ in b] for _ in a]
for ii, i in enumerate(a):
for jj, j in enumerate(b):
if prime_judge(i + j):
l[ii][jj] = 1
return l```

(4)a = [5, 13]，b = [2, 6]

 5 13 2 1 0 6 1 1

(5) Write recursive function find and use Hungarian algorithm to find the optimal combination

```def find(x):
for index in range(len(b)):
if matrix[x][index] == 1 and used_b[index] == 0:
used_b[index] = 1
if conection_b[index] == -1 or find(conection_b[index]) != 0:
conection_b[index] = x
return 1
return 0```

(6) Sample analysis of execution steps of find function

According to the corresponding relationship between x and y in the figure above, the following matrix can be constructed

 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1 x4 0 0 1 1 0 1 0 x5 0 0 0 1 0 0 0 x6 0 0 0 1 0 0 0

(7) The outermost loops x1 to x6, i.e. the first line to the sixth line, are traversed from y1 to y7 respectively

(8) Where used_b = [0, 0, 0, 0, 0, 0, 0] is y1 used in a row

(9)conection_b = [-1,-1,-1,-1,-1,-1,-1], where the value range of each element is 0-5, representing the row x corresponding to y

(10) Starting from the first line, y1, conection is selected_ B changes [0, - 1, - 1, - 1, - 1, - 1, - 1, - 1]

```i: 0
find: 0
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [-1, -1, -1, -1, -1, -1, -1]
index: 0
conection_b: [0, -1, -1, -1, -1, -1, -1]
count```
 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0

(11) In the second row, y2, conection is selected_ B changes [0, 1, - 1, - 1, - 1, - 1, - 1]

```i: 1
find: 1
_index: 1
_used_b: [0, 1, 0, 0, 0, 0, 0]
_conection_b: [0, -1, -1, -1, -1, -1, -1]
index: 1
conection_b: [0, 1, -1, -1, -1, -1, -1]
count```
 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0

(11) In the third row, y1 is selected. Since y1 is also selected in the first row, recursion is entered

```i: 2
find: 2
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 0
_index: 1
_used_b: [1, 1, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 1
_index: 4
_used_b: [1, 1, 0, 0, 1, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
index: 4
conection_b: [0, 1, -1, -1, 1, -1, -1]
index: 1
conection_b: [0, 0, -1, -1, 1, -1, -1]
index: 0
conection_b: [2, 0, -1, -1, 1, -1, -1]
count```
 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1

(12) Get that the index of the conflicting row is 0, so start finding (0), and find that y2 is also used, so continue to recursively find(1)

 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1

(13) Finally x2 finds y5, so the recursion ends_ b: [2, 0, -1, -1, 1, -1, -1]

 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1

(14) In the fourth row, y3 is selected. Since there is no conflict, there is no conflict_ b: [2, 0, 3, -1, 1, -1, -1]

```i: 3
find: 3
_index: 2
_used_b: [0, 0, 1, 0, 0, 0, 0]
_conection_b: [2, 0, -1, -1, 1, -1, -1]
index: 2
conection_b: [2, 0, 3, -1, 1, -1, -1]
count```
 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1 x4 0 0 1 1 0 1 0

(14) In the fifth row, y4 is selected. Since there is no conflict, there is no conflict_ b: [2, 0, 3, 4, 1, -1, -1]

```i: 4
find: 4
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, -1, 1, -1, -1]
index: 3
conection_b: [2, 0, 3, 4, 1, -1, -1]
count```
 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1 x4 0 0 1 1 0 1 0 x5 0 0 0 1 0 0 0

(14) In the sixth row, y4 is selected. Because it conflicts with the fifth row, it enters recursive find(4)

 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1 x4 0 0 1 1 0 1 0 x5 0 0 0 1 0 0 0 x6 0 0 0 1 0 0 0
```i: 5
find: 5
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, 4, 1, -1, -1]
find: 4
used_b: [0, 0, 0, 1, 0, 0, 0]
conection_b: [2, 0, 3, 4, 1, -1, -1]
5```

(15) Because there are no other optional line items except y4 in the fifth row, so   find(4) = 0，conection_b has not been changed, so: conection_b: [2, 0, 3, 4, 1, -1, -1]

 y1 y2 y3 y4 y5 y6 y7 x1 1 1 0 1 0 0 0 x2 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 1 x4 0 0 1 1 0 1 0 x5 0 0 0 1 0 0 0 x6 0 0 0 1 0 0 0
```>>>def find(x):
...    print("find:", x)
...    for index in range(7):
...        if matrix[x][index] == 1 and used_b[index] == 0:
...            used_b[index] = 1
...            print("_index:", index)
...            print("_used_b:", str(used_b))
...            print("_conection_b:", str(conection_b))
...            if conection_b[index] == -1 or find(conection_b[index]) != 0:
...                print("index:", index)
...                conection_b[index] = x
...                print("conection_b:", str(conection_b))
...                return 1
...    return 0
>>>matrix = [
...    [1,1,0,1,0,0,0],
...    [0,1,0,0,1,0,0],
...    [1,0,0,1,0,0,1],
...    [0,0,1,1,0,1,0],
...    [0,0,0,1,0,0,0],
...    [0,0,0,1,0,0,0]
...    ]
>>>conection_b = [-1 for _ in range(7)]
>>>count = 0
>>>for i in range(6):
...    used_b = [0 for _ in range(7)]
...    print("i:",i)
...    if find(i):
...        print("count")
...        count += 1
>>>print("used_b:", str(used_b))
>>>print("conection_b:", str(conection_b))
>>>print(count)
i: 0
find: 0
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [-1, -1, -1, -1, -1, -1, -1]
index: 0
conection_b: [0, -1, -1, -1, -1, -1, -1]
count
i: 1
find: 1
_index: 1
_used_b: [0, 1, 0, 0, 0, 0, 0]
_conection_b: [0, -1, -1, -1, -1, -1, -1]
index: 1
conection_b: [0, 1, -1, -1, -1, -1, -1]
count
i: 2
find: 2
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 0
_index: 1
_used_b: [1, 1, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 1
_index: 4
_used_b: [1, 1, 0, 0, 1, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
index: 4
conection_b: [0, 1, -1, -1, 1, -1, -1]
index: 1
conection_b: [0, 0, -1, -1, 1, -1, -1]
index: 0
conection_b: [2, 0, -1, -1, 1, -1, -1]
count
i: 3
find: 3
_index: 2
_used_b: [0, 0, 1, 0, 0, 0, 0]
_conection_b: [2, 0, -1, -1, 1, -1, -1]
index: 2
conection_b: [2, 0, 3, -1, 1, -1, -1]
count
i: 4
find: 4
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, -1, 1, -1, -1]
index: 3
conection_b: [2, 0, 3, 4, 1, -1, -1]
count
i: 5
find: 5
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, 4, 1, -1, -1]
find: 4
used_b: [0, 0, 0, 1, 0, 0, 0]
conection_b: [2, 0, 3, 4, 1, -1, -1]
5```

summary

The core idea of the Hungarian algorithm is: give priority to the last row. If there is a conflict, look for the replaceable item of the conflicting row. If there is no replaceable item, discard the last row. If there is a replaceable item, use it for substitution. If there is a conflict after substitution, enter recursion. If it is found that the conflict cannot be resolved, discard the last row and the conflict can be resolved, Use this scheme.

code

```def prime_judge(n):
m = int(n ** 0.5) + 2
for i in range(3, m, 2):
if n % i == 0:
return False
return True

def group_lst(lst): ##Partial parity
a, b = [], []
for i in lst:
if int(i) % 2 == 0:
a.append(int(i))
else:
b.append(int(i))
return a, b

def matrix_ab(a, b):
l = [[0 for _ in b] for _ in a]
for ii, i in enumerate(a):
for jj, j in enumerate(b):
if prime_judge(i + j):
l[ii][jj] = 1
return l

def find(x):
for index in range(len(b)):
if matrix[x][index] == 1 and used_b[index] == 0:
used_b[index] = 1
if conection_b[index] == -1 or find(conection_b[index]) != 0:
conection_b[index] = x
return 1
return 0

while True:
try:
n = int(input())
m = input().split(' ')
a, b = group_lst(m)
matrix = matrix_ab(a, b)
conection_b = [-1 for _ in range(len(b))]
count = 0
for i in range(len(a)):
used_b = [0 for _ in range(len(b))]
if find(i):
count += 1
print(count)
except:
break```

Reference

https://www.nowcoder.com/ta/huawei/

https://blog.csdn.net/weixin_37474682/article/details/119899324

Added by wdseelig on Mon, 06 Sep 2021 02:37:37 +0300