题目51：找出最小的能够通过改变同一部分得到八个质数的质数。,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2015-5-29 23:02:42

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

Prime digit replacements

By replacing thedigit 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 theanddigits 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 发表于 2016-10-12 17:22:52

本帖最后由 jerryxjr1220 于 2017-10-9 11:28 编辑

121313
Execution took 0.761506 seconds

import math
import time

def primes1(n):
""" Returnsa list of primes < n """
sieve = * int(n/2)
for i in range(3,int(n**0.5)+1,2):
   if sieve:
         sieve = * int((n-i*i-1)/(2*i)+1)
return + ]

def is_prime(x):
up_bound = int(math.floor(math.sqrt(x)))
for i in range(2,up_bound+1):
   if x % i == 0:
         return False
return True

start = time.time()
primes = primes1(1000000)
primes =
found = False
for prime in primes:
for i in range(0,len(set(str(prime)))):
   if found == True:
         break
   if sorted(str(prime)) == sorted(set(str(prime))):
         continue
   else:
         if int(sorted(str(prime))) > 2:
            break
         elif int(sorted(str(prime))) == 1:
            man_prime = str(prime)
            man_list = list(man_prime)
            count = 1
            for j in range(2,10):
               indices =
               for k in range(0,len(man_prime)):
                     if k in indices:
                        man_list = str(j)
               man_prime = "".join(man_list)
               if is_prime(int(man_prime)):
                     count += 1
               else:
                     pass
            if count >= 8:
               print (prime)
               found = True
         else:
            man_prime = str(prime)
            man_list = list(man_prime)
            count = 1
            for j in range(1,10):
               indices =
               for k in range(0,len(man_prime)):
                     if k in indices:
                        man_list = str(j)
               man_prime = "".join(man_list)
               if is_prime(int(man_prime)):
                     count += 1
               else:
                     pass
            if count >= 8:
               print (prime)
               break
elapsed = time.time() -start

print ("Execution took {:5f} seconds".format(elapsed))

from itertools import combinations
def isprime(n):
if n%2==0: return False
for i in range(3,int(n**0.5+1),2):
if n%i==0: return False
return True

def gen_replaced_num(snum,n=2):
M = []
for c in combinations(range(len(snum)),n):
slst = list(snum)
m = []
for num in range(10):
ss = slst.copy()
for i in c:
ss = str(num)
if ss == '0': continue
m.append(int(''.join(ss)))
M.append(m)
return M

for i in range(100000,1000000):
for eachgroup in gen_replaced_num(str(i),3):
if sum(1 for each in eachgroup if isprime(each))>=8:
print (eachgroup)
exit()

芒果加黄桃 发表于 2017-1-17 11:44:06

本帖最后由芒果加黄桃于 2017-1-17 11:50 编辑

# encoding:utf-8
# 置换质数中两位数字，能得到最少8个质数，找出最小的
from time import time
from itertools import combinations
def getPrimes(N):
primes = * N
primes, primes = False, False
for i, prime in enumerate(primes):
   if prime:
         for j in range(i * i, N, i):
            primes = False
return
def euler051(N=1000000):
l_pr = getPrimes(N)
s_all = set()
l_primes =
l_combs = , 2)]
l_combs.sort(reverse=True)
for tmp in l_combs:
   print('替换位数：',tmp)
   solid = list(s_all - set(tmp))
   for i in range(0, len(l_primes)):
         count = 0
         l_nums = )]
         for j in range(i + 1, len(l_primes)):
            t1 = l_primes
            t2 = l_primes
            if ((t1)] == t2]
               and t1] == t2]
               and t1] == t2]):
               count += 1
               l_nums.append(int(l_primes))
               if count >= 7:
                     print(l_nums)
                     return
if __name__ == '__main__':
start = time()
euler051()
print('cost %.6f sec' % (time() - start))

替换位数： (3, 4)

cost 0.418042 sec

芒果加黄桃 发表于 2017-1-17 11:50:36

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

替换位数： (3, 4)

老大，帮看看对么

jerryxjr1220 发表于 2017-1-17 11:51:03

芒果加黄桃发表于 2017-1-17 11:44
替换位数： (3, 4)

cost 0.418042 sec

看小练习答案吧
http://bbs.fishc.com/forum.php?mod=viewthread&tid=80348&extra=page%3D1%26filter%3Dtypeid%26typeid%3D497

芒果加黄桃 发表于 2017-1-17 12:40:04

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

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

渡风发表于 2017-6-15 09:47:33

本帖最后由渡风于 2017-6-15 09:51 编辑

此代码使用matlab编程
Problem51所用时间为7.2791秒
Problem51的答案为121313
%% Problem51.m
% 最后编辑时间：17-06-15 8:20
% 问题：找出最小的能够通过改变同一部分得到八个质数的质数。
% 从一个质数的同时为 0 1 2的部分开始改变
% 而且个位数不参与置换,
% 隐约感觉只是置换一个位数，也不会得到结果。
% 此代码使用matlab编程
% Problem51所用时间为7.2791秒
% Problem51的答案为121313
function Output = Problem51()
tic
%先刷出100w一下的质数
n = 1000000;
Vector = GetPrime(n);
Vec = Vector(Vector > 56003); %56003是可以刷出7个质数的最小数

N = length(Vec);
for ii = 1:N
if PrimeNum(Vec(ii)) == 1
   Output = Vec(ii);
   break
end
end

toc
disp('此代码使用matlab编程')
disp(['Problem51所用时间为',num2str(toc),'秒'])
disp(['Problem51的答案为',num2str(Output)])
end
% 输入一个质数，得到其置换某几个位数,若等于8，返回 1 否则返回 0
% 细节：置换其可能的0 1 2 ，最后一位不进行置换
function Judge = PrimeNum(N)
if nargin == 0
N = 197;
end
Str = num2str(N);
Real = Str(1:end-1);
L = length(Real);

Store = 0;
for ii =1:3
L(ii) = length(regexp(Real,num2str(ii - 1)));
Out = 0;
Total = 0;
if L(ii) >= 2
   for jj = 0:9
         S = Str;
         S(regexp(Real,num2str(ii - 1))) = num2str(jj);
         if isprime(str2double(S)) == 1
               if strcmp(S(1),'0') ~= 1
                  Total = Total + 1;
               end
         else
               Out = Out + 1;
         end

         if Out >= 3
               break
         end
   end
end
if Total >= Store
   Store = Total;
end
end

if Store == 8
Judge = 1;
else
Judge = 0;
end
end
%% 得到n以下的所有质数
function Vector = GetPrime(n)
if nargin == 0
n = 10000;
end

Judge = ones(1,n-1);
Judge(1) = 0;
for ii = 1:n-1
if Judge(ii) == 1
   for jj = 2*ii : ii : n-1
         Judge(jj) = 0;
   end
end
end
Vector = find(Judge == 1);
end

ft215378 发表于 2021-10-24 19:57:50

本帖最后由 ft215378 于 2021-10-24 19:59 编辑

#找出最小的能够通过改变同一部分得到八个质数的质数
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 = j
         num_list = j
         num_list = 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:
         total += str(each)
   result = 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
   for each in tar:
         if is_prime(each):
            result.append(each)
   if len(result) == 8 and result > 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 发表于 2022-1-8 20:01:34

本帖最后由 guosl 于 2022-1-8 20:17 编辑

假设找到的满足条件的最小素数是x，则x中可以替换的数字一定是小于等2的，否则是无法得到八个不同的素数，故编程思路是：
1. 从11开始由小到大枚举素数x；
2. 逐位查找x中是否有小于等于2的数字，把这些数字统一替换成其它的数字，看看是否可以得到八个不同的素数。
3. 为了加快程序运行的速度，我采用了OpenMP平行编程。
/*
答案：121313
耗时：0.0167028秒（单核）
   0.0031306秒（六核）
*/
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <omp.h>
using namespace std;

char cp;//打表用来判断小的正整数是否是素数
vector<int> vp;//打表用来判断大的正整数是否是素数
//每次计算的工作量
//减少进入临界区次数
int nSteps = 100;

bool isp(int n) //判断n是否是素数
{
if (n <= 1000000) //小正整数
return (cp == 1);
//大整数用除了判断
int d = (int)sqrt((double)n);
for (int i = 0; i < (int)vp.size() && vp <= d; ++i)
{
if (n%vp == 0)
   return false;
}
return true;
}

int main(void)
{
//筛法求素数
memset(cp, 1, sizeof(cp));
cp = 0;
cp = 0;
for (int i = 2; i <= 1000; ++i)
{
if (cp == 0)
   continue;
for (int j = i * i; j <= 1000000; j += i)
   cp = 0;
}
vp.push_back(2);
for (int i = 3; i < 1000000; i += 2)
{
if (cp == 1)
   vp.push_back(i);
}
volatile bool bContinue = true;//循环是否进行下去的标志
volatile int k = 4; //循环变量
volatile int nMinp = 0x7fffffff; //记录最终结果
#pragma omp parallel shared(bContinue,k,vp,cp,nMinp)
while (bContinue) //进入并行循环
{
int k1;
#pragma omp critical(c1)
{
   k1 = k; //获取当前计算的值
   k += nSteps; //循环变量递增
}
char strNum;
char cChoice;
for (int k2 = k1; bContinue && k2 < (int)vp.size() && (k2 < k1 + nSteps); ++k2) //枚举素数
{
   _itoa_s(vp, strNum, 10);//将数转化成字符串
   //因为要求最小的满足条件的素数
   //所以可改动位上的最小数字一定不大于2
   for (char c = '0'; c <= '2'; ++c) //查找可以替换的数字
   {
   int nCount = 0;//记录可替换数字的个数
   memset(cChoice, 0, sizeof(cChoice));
   for (int i = 0; i < (int)strlen(strNum); ++i) //查找可变动的位，并标志出来
   {
      if (strNum == c)
      {
         cChoice = 1;//记录哪些位置上可以被替换
         ++nCount;
      }
   }
   if (nCount > 0) //有可以改动的位存在
   {
      nCount = 1;//记录替换后得到不同的素数个数，本身就满足条件
      for (int i = (int)(c - '0') + 1; i < 10; ++i) //替换成其它数字
      {
         int y = 0;
         for (int j = 0; j < (int)strlen(strNum); ++j) //计算替换后的值
         {
         y *= 10;
         if (cChoice == 1)
            y += i; //替换
         else
            y += int(strNum - 48);
         }
         if (isp(y)) //判断替换后所得的数是否是素数
         ++nCount; //记录成为素数的个数
      }
      if (nCount >= 8) //如果大于等于8
      {
         if (nMinp > vp)
         {
#pragma omp critical
         {
            nMinp = vp;
            bContinue = false;
         }
         }
      }
   }
   }
}
}
cout << nMinp << endl;
return 0;
}

页: [1]

鱼C论坛's Archiver

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