题目51：找出最小的能够通过改变同一部分得到八个质数的质数。

欧拉计划

Prime digit replacements

By replacing the digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the and digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

题目：

通过置换 *3 的第一位得到的 9 个数中，有六个是质数：13, 23, 43, 53, 73 和 83。

通过用同样的数字置换 56**3 的第三位和第四位，这个五位数是第一个能够得到七个质数的数字，得到的质数是：56003, 56113, 56333, 56443, 56663, 56773, 和 56993。因此其中最小的 56003 就是具有这个性质的最小的质数。

找出最小的质数，通过用同样的数字置换其中的一部分（不一定是相邻的部分），能够得到八个质数。

jerryxjr1220

121313
Execution took 0.761506 seconds

1. import math
   
2. import time
   
3. 
   
4. def primes1(n):
   
5.     """ Returns  a list of primes < n """
   
6.     sieve = [True] * int(n/2)
   
7.     for i in range(3,int(n**0.5)+1,2):
   
8.         if sieve[int(i/2)]:
   
9.             sieve[int(i*i/2):n:i] = [False] * int((n-i*i-1)/(2*i)+1)
   
10.     return [2] + [2*i+1 for i in range(1,int(n/2)) if sieve[i]]
    
11. 
    
12. def is_prime(x):
    
13.     up_bound = int(math.floor(math.sqrt(x)))
    
14.     for i in range(2,up_bound+1):
    
15.         if x % i == 0:
    
16.             return False
    
17.     return True
    
18. 
    
19. 
    
20. start = time.time()
    
21. primes = primes1(1000000)
    
22. primes = [prime for prime in primes if prime > 100000  and len(set(str(prime))) + 1 < len(str(prime))]
    
23. found = False
    
24. for prime in primes:
    
25.     for i in range(0,len(set(str(prime)))):
    
26.         if found == True:
    
27.             break
    
28.         if sorted(str(prime))[i] == sorted(set(str(prime))):
    
29.             continue
    
30.         else:
    
31.             if int(sorted(str(prime))[i]) > 2:
    
32.                 break
    
33.             elif int(sorted(str(prime))[i]) == 1:
    
34.                 man_prime = str(prime)
    
35.                 man_list = list(man_prime)
    
36.                 count = 1
    
37.                 for j in range(2,10):
    
38.                     indices = [i for i, x in enumerate(str(prime)) if x == '1']
    
39.                     for k in range(0,len(man_prime)):
    
40.                         if k in indices:
    
41.                            man_list[k] = str(j)
    
42.                     man_prime = "".join(man_list)
    
43.                     if is_prime(int(man_prime)):
    
44.                         count += 1
    
45.                     else:
    
46.                         pass
    
47.                 if count >= 8:
    
48.                    print (prime)
    
49.                    found = True
    
50.             else:
    
51.                 man_prime = str(prime)   
    
52.                 man_list = list(man_prime)
    
53.                 count = 1
    
54.                 for j in range(1,10):
    
55.                     indices = [i for i, x in enumerate(str(prime)) if x == '1']
    
56.                     for k in range(0,len(man_prime)):
    
57.                         if k in indices:
    
58.                            man_list[k] = str(j)
    
59.                     man_prime = "".join(man_list)
    
60.                     if is_prime(int(man_prime)):
    
61.                         count += 1
    
62.                     else:
    
63.                         pass
    
64.                 if count >= 8:
    
65.                    print (prime)
    
66.                    break
    
67. elapsed = time.time() -start
    
68. 
    
69. print ("Execution took {:5f} seconds".format(elapsed))

复制代码

1. from itertools import combinations
   
2. def isprime(n):
   
3.         if n%2==0: return False
   
4.         for i in range(3,int(n**0.5+1),2):
   
5.                 if n%i==0: return False
   
6.         return True
   
7. 
   
8. def gen_replaced_num(snum,n=2):
   
9.         M = []
   
10.         for c in combinations(range(len(snum)),n):
    
11.                 slst = list(snum)
    
12.                 m = []
    
13.                 for num in range(10):
    
14.                         ss = slst.copy()
    
15.                         for i in c:
    
16.                                 ss[i] = str(num)
    
17.                         if ss[0] == '0': continue
    
18.                         m.append(int(''.join(ss)))
    
19.                 M.append(m)
    
20.         return M
    
21. 
    
22. for i in range(100000,1000000):
    
23.         for eachgroup in gen_replaced_num(str(i),3):
    
24.                 if sum(1 for each in eachgroup if isprime(each))>=8:
    
25.                         print (eachgroup[0])
    
26.                         exit()

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 置换质数中两位数字，能得到最少8个质数，找出最小的
   
3. from time import time
   
4. from itertools import combinations
   
5. def getPrimes(N):
   
6.     primes = [True] * N
   
7.     primes[0], primes[1] = False, False
   
8.     for i, prime in enumerate(primes):
   
9.         if prime:
   
10.             for j in range(i * i, N, i):
    
11.                 primes[j] = False
    
12.     return [k for k, p in enumerate(primes) if p ]
    
13. def euler051(N=1000000):
    
14.     l_pr = getPrimes(N)
    
15.     s_all = set([0, 1, 2, 3, 4, 5])
    
16.     l_primes = [str(x) for x in l_pr if x > 56000 and x < 100000]
    
17.     l_combs = [x for x in combinations([1, 2, 3, 4], 2)]
    
18.     l_combs.sort(reverse=True)
    
19.     for tmp in l_combs:
    
20.         print('替换位数：',tmp)
    
21.         solid = list(s_all - set(tmp))
    
22.         for i in range(0, len(l_primes)):
    
23.             count = 0
    
24.             l_nums = [int(l_primes[i])]
    
25.             for j in range(i + 1, len(l_primes)):
    
26.                 t1 = l_primes[i]
    
27.                 t2 = l_primes[j]
    
28.                 if ((t1)[solid[0]] == t2[solid[0]]
    
29.                     and t1[solid[1]] == t2[solid[1]]
    
30.                     and t1[solid[2]] == t2[solid[2]]):
    
31.                     count += 1
    
32.                     l_nums.append(int(l_primes[j]))
    
33.                     if count >= 7:
    
34.                         print(l_nums)
    
35.                         return
    
36. if __name__ == '__main__':
    
37.     start = time()
    
38.     euler051()
    
39.     print('cost %.6f sec' % (time() - start))
    

复制代码

替换位数： (3, 4)
[56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093]
cost 0.418042 sec

芒果加黄桃

jerryxjr1220 发表于 2016-10-12 17:22
121313
Execution took 0.761506 seconds

替换位数： (3, 4)
[56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093]

老大，帮看看对么

jerryxjr1220

芒果加黄桃 发表于 2017-1-17 11:44
替换位数： (3, 4)
[56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093]
cost 0.418042 sec

看小练习答案吧
http://bbs.fishc.com/forum.php?m ... peid%26typeid%3D497

芒果加黄桃

jerryxjr1220 发表于 2017-1-17 11:51
看小练习答案吧
http://bbs.fishc.com/forum.php?mod=viewthread&tid=80348&extra=page%3D1%26filter%3D ...

没注意相同数字替换，多谢~

渡风

此代码使用matlab编程
Problem51所用时间为7.2791秒
Problem51的答案为121313

1. %% Problem51.m
   
2. % 最后编辑时间：17-06-15 8:20
   
3. % 问题：找出最小的能够通过改变同一部分得到八个质数的质数。
   
4. % 从一个质数的 同时为 0 1 2的部分开始改变
   
5. % 而且个位数不参与置换,
   
6. % 隐约感觉只是置换一个位数，也不会得到结果。
   
7. % 此代码使用matlab编程
   
8. % Problem51所用时间为7.2791秒
   
9. % Problem51的答案为121313
   
10. function Output = Problem51()
    
11. tic
    
12. %先刷出100w一下的质数
    
13. n = 1000000;
    
14. Vector = GetPrime(n);
    
15. Vec = Vector(Vector > 56003); %56003是可以刷出7个质数的最小数
    
16. 
    
17. N = length(Vec);
    
18. for ii = 1:N
    
19.     if PrimeNum(Vec(ii)) == 1
    
20.         Output = Vec(ii);
    
21.         break
    
22.     end
    
23. end
    
24. 
    
25. toc
    
26. disp('此代码使用matlab编程')
    
27. disp(['Problem51所用时间为',num2str(toc),'秒'])
    
28. disp(['Problem51的答案为',num2str(Output)])
    
29. end
    
30. % 输入一个质数，得到其置换某几个位数,若等于8，返回 1 否则返回 0
    
31. % 细节：置换其可能的0 1 2 ，最后一位不进行置换
    
32. function Judge = PrimeNum(N)
    
33. if nargin == 0
    
34. N = 197;
    
35. end
    
36. Str = num2str(N);
    
37. Real = Str(1:end-1);
    
38. L = length(Real);
    
39. 
    
40. Store = 0;
    
41. for ii =1:3
    
42.     L(ii) = length(regexp(Real,num2str(ii - 1)));
    
43.     Out = 0;
    
44.     Total = 0;
    
45.     if L(ii) >= 2
    
46.         for jj = 0:9
    
47.             S = Str;
    
48.             S(regexp(Real,num2str(ii - 1))) = num2str(jj);
    
49.               if isprime(str2double(S)) == 1
    
50.                   if strcmp(S(1),'0') ~= 1
    
51.                      Total = Total + 1;
    
52.                   end
    
53.               else
    
54.                   Out = Out + 1;
    
55.               end
    
56.               
    
57.               if Out >= 3
    
58.                   break
    
59.               end
    
60.         end
    
61.     end
    
62.     if Total >= Store
    
63.         Store = Total;
    
64.     end
    
65. end
    
66. 
    
67. if Store == 8
    
68.     Judge = 1;
    
69. else
    
70.     Judge = 0;
    
71. end
    
72. end
    
73. %% 得到n以下的所有质数
    
74. function Vector = GetPrime(n)
    
75. if nargin == 0
    
76. n = 10000;
    
77. end
    
78. 
    
79. Judge = ones(1,n-1);
    
80. Judge(1) = 0;
    
81. for ii = 1:n-1
    
82.     if Judge(ii) == 1
    
83.         for jj = 2*ii : ii : n-1
    
84.             Judge(jj) = 0;
    
85.         end
    
86.     end
    
87. end
    
88. Vector = find(Judge == 1);
    
89. end
    

复制代码

ft215378

#找出最小的能够通过改变同一部分得到八个质数的质数
from itertools import *
from time import *
from math import *

#验证是否是质数
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for a in range(3,int(sqrt(number) + 1),2):
            if number % a == 0:
                return False
        return True
    return False

#质数生成器
def get_prime(number):
    while True:
        if is_prime(number):
            yield number
        number += 1

#生成n位数的质数列表
def prime_list(n):
    start = int('1' + '0'*(n-1))
    end = int('9'*n)
    prime = []
    for i in get_prime(start):
        if i > end:
            break
        prime.append(i)
    return prime

#置换一次
def change(num, pos1=None, pos2=None, pos3= None):
    a = str(num)
    result = []
    num_list = []
    for i in a:
        num_list.append(int(i))
    x= num_list
    j = 0
    while True:
        try:
            num_list[pos1] = j
            num_list[pos2] = j
            num_list[pos3] = j
        except TypeError:
            pass
        finally:
            result.append(num_list)
            num_list = x.copy()
            j += 1
        if j == 10:
            break
    index = 0
    total = ''
    while True:
        for each in result[index]:
            total += str(each)
        result[index] = int(total)
        total = ''
        index += 1
        if index == len(result):
            break
    return result

#全部置换
def change_all(num):
    change_num = []
    for a in range(1, 5):
        for b in range((a+1), 6):
            change_num.extend(change(num,a, b))
    for a in range(4):
        for b in range((a+1), 5):
            for c in range((b+1), 6):
                change_num.extend(change(num,a, b, c))
               
    return change_num

#判断结果
def is_eight(seq):
    n = 0
    result = []
    while True:
        tar = seq[n:(n+10)]
        for each in tar:
            if is_prime(each):
                result.append(each)
        if len(result) == 8 and result[0] > 99999:
            return True
        result = []
        n += 10
        if n == len(seq) - 10:
           break


start = time()
for each in prime_list(6):
    if is_eight(change_all(each)):
        print(each)
        break
end = time()
print("用时%.4f秒" % (end-start))
#'''

代码较长但是结果
120383
用时6.9996秒
并不是121313

guosl

假设找到的满足条件的最小素数是x，则x中可以替换的数字一定是小于等2的，否则是无法得到八个不同的素数，故编程思路是：
1. 从11开始由小到大枚举素数x；
2. 逐位查找x中是否有小于等于2的数字，把这些数字统一替换成其它的数字，看看是否可以得到八个不同的素数。
3. 为了加快程序运行的速度，我采用了OpenMP平行编程。

1. /*
   
2. 答案：121313
   
3. 耗时：0.0167028秒（单核）
   
4.       0.0031306秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <vector>
   
8. #include <cstdlib>
   
9. #include <cstring>
   
10. #include <cmath>
    
11. #include <omp.h>
    
12. using namespace std;
    
13. 
    
14. char cp[1000004];//打表用来判断小的正整数是否是素数
    
15. vector<int> vp;//打表用来判断大的正整数是否是素数
    
16. //每次计算的工作量
    
17. //减少进入临界区次数
    
18. int nSteps = 100;
    
19. 
    
20. bool isp(int n) //判断n是否是素数
    
21. {
    
22.   if (n <= 1000000) //小正整数
    
23.     return (cp[n] == 1);
    
24.   //大整数用除了判断
    
25.   int d = (int)sqrt((double)n);
    
26.   for (int i = 0; i < (int)vp.size() && vp[i] <= d; ++i)
    
27.   {
    
28.     if (n%vp[i] == 0)
    
29.       return false;
    
30.   }
    
31.   return true;
    
32. }
    
33. 
    
34. int main(void)
    
35. {
    
36.   //筛法求素数
    
37.   memset(cp, 1, sizeof(cp));
    
38.   cp[0] = 0;
    
39.   cp[1] = 0;
    
40.   for (int i = 2; i <= 1000; ++i)
    
41.   {
    
42.     if (cp[i] == 0)
    
43.       continue;
    
44.     for (int j = i * i; j <= 1000000; j += i)
    
45.       cp[j] = 0;
    
46.   }
    
47.   vp.push_back(2);
    
48.   for (int i = 3; i < 1000000; i += 2)
    
49.   {
    
50.     if (cp[i] == 1)
    
51.       vp.push_back(i);
    
52.   }
    
53.   volatile bool bContinue = true;//循环是否进行下去的标志
    
54.   volatile int k = 4; //循环变量
    
55.   volatile int nMinp = 0x7fffffff; //记录最终结果
    
56. #pragma omp parallel shared(bContinue,k,vp,cp,nMinp)
    
57.   while (bContinue) //进入并行循环
    
58.   {
    
59.     int k1;
    
60. #pragma omp critical(c1)
    
61.     {
    
62.       k1 = k; //获取当前计算的值
    
63.       k += nSteps; //循环变量递增
    
64.     }
    
65.     char strNum[12];
    
66.     char cChoice[12];
    
67.     for (int k2 = k1; bContinue && k2 < (int)vp.size() && (k2 < k1 + nSteps); ++k2) //枚举素数
    
68.     {
    
69.       _itoa_s(vp[k2], strNum, 10);//将数转化成字符串
    
70.       //因为要求最小的满足条件的素数
    
71.       //所以可改动位上的最小数字一定不大于2
    
72.       for (char c = '0'; c <= '2'; ++c) //查找可以替换的数字
    
73.       {
    
74.         int nCount = 0;//记录可替换数字的个数
    
75.         memset(cChoice, 0, sizeof(cChoice));
    
76.         for (int i = 0; i < (int)strlen(strNum); ++i) //查找可变动的位，并标志出来
    
77.         {
    
78.           if (strNum[i] == c)
    
79.           {
    
80.             cChoice[i] = 1;//记录哪些位置上可以被替换
    
81.             ++nCount;
    
82.           }
    
83.         }
    
84.         if (nCount > 0) //有可以改动的位存在
    
85.         {
    
86.           nCount = 1;//记录替换后得到不同的素数个数，本身就满足条件
    
87.           for (int i = (int)(c - '0') + 1; i < 10; ++i) //替换成其它数字
    
88.           {
    
89.             int y = 0;
    
90.             for (int j = 0; j < (int)strlen(strNum); ++j) //计算替换后的值
    
91.             {
    
92.               y *= 10;
    
93.               if (cChoice[j] == 1)
    
94.                 y += i; //替换
    
95.               else
    
96.                 y += int(strNum[j] - 48);
    
97.             }
    
98.             if (isp(y)) //判断替换后所得的数是否是素数
    
99.               ++nCount; //记录成为素数的个数
    
100.           }
     
101.           if (nCount >= 8) //如果大于等于8
     
102.           {
     
103.             if (nMinp > vp[k2])
     
104.             {
     
105. #pragma omp critical
     
106.               {
     
107.                 nMinp = vp[k2];
     
108.                 bContinue = false;
     
109.               }
     
110.             }
     
111.           }
     
112.         }
     
113.       }
     
114.     }
     
115.   }
     
116.   cout << nMinp << endl;
     
117.   return 0;
     
118. }
     

复制代码