题目49：找出由互为排列的4位数质数组成的序列
Prime permutationsThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
题目：
1487, 4817, 8147 这个序列，每个比前一个递增 3330，而且这个序列有两个特点：1. 序列中的每个数都是质数。 2. 每个四位数都是其他数字的一种排列。
1，2，3 位组成的三个质数的序列中没有具有以上性质的。但是还有另外一个四位的递增序列满足这个性质。
如果将这另外一个序列的三个数连接起来，组成的 12 位数字是多少？
本帖最后由 jerryxjr1220 于 2016-10-12 16:24 编辑
另外4位数字是：2969 6299 9629
def isPrime(num):
if num == 2:
return True
elif num % 2 == 0:
return False
else:
for i in range(3,int(num**0.5+1),2):
if num % i == 0:
return False
return True
def main():
primes = sorted()
for a in primes:
b = a + 3330
c = b + 3330
# test 1: are primes
if b in primes and c in primes:
# test 2: are permutations of each other
if set(sorted(list(str(a)))) == set(sorted(list(str(b)))) == set(sorted(list(str(c)))):
print (a, b, c)
main() from itertools import permutations as per
def isprime(n):
if n <= 1: return False
if n == 2: return True
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
for i in per(,3):
if i > 3: break
n = i*100+i*10+i
if sorted(list(str(n))) == sorted(list(str(n + 333))) == sorted(list(str(n + 666))):
for j in :
if isprime(n*10+j) and isprime(n*10+j+3330) and isprime(n*10+j+6660):
if n*10+j != 1487:
print(n*10+j,n*10+j+3330,n*10+j+6660,sep = '') import math
def Prime(x):
if x >1:
if x==2:
return True
if x%2==0:
return False
for i in range(3,int(math.sqrt(x)+1),2):
if x%i==0:
return False
return True
return False
list1=[]
for i in range(1000,10000):
if Prime(i):
list1.append(i)
for i in list1:
j = 1000
while True:
tmp = False
if i+j in list1 and i+2*j in list1:
tmp = True
if tmp:
a=set(str(i))
b=set(str(i+j))
c = set(str(i+2*j))
if a==b and b==c:
print(i,i+j,i+2*j)
break
else:
tmp = False
if not tmp:
j+=10
if i+2*j>list1[-1]:
break
运行结果：
1487 4817 8147
2969 6299 9629 本帖最后由 芒果加黄桃 于 2017-1-16 15:22 编辑
# encoding:utf-8
# 1487 4817 8147 都是质数 等差数列找另外一组类似的四位数
from time import time
from itertools import permutations
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 isSeq(s_nums):
l_sums = list(s_nums)
l_sums.sort()
for i in range(0, len(l_sums)):
for j in range(i + 1, len(l_sums)):
for k in range(j + 1, len(l_sums)):
if l_sums - l_sums == l_sums - l_sums:
print(l_sums, l_sums, l_sums)
def euler049(N=10000):
s_primes = set(getPrimes(N))
s_pass = set()
for each in s_primes:
if each in s_pass:
continue
l_tmp = list(str(each))
s_tmp = set()
for tt in permutations(l_tmp, 4):
s = ''
for t in tt:
s += t
s_tmp.add(int(s))
joint_set = s_primes & s_tmp
s_pass = s_pass | joint_set
if len(joint_set) >= 3:
isSeq(joint_set)
if __name__ == '__main__':
start = time()
euler049()
print('cost %.6f sec' % (time() - start))
2969 6299 9629
1487 4817 8147
cost 0.022000 sec
完成后学习了其他几位老大的程序，发现原来还有差值3330这个条件可以用.... %% Problem49.m
%最后编辑时间：2017-06-14 11:13 版本1.0
%找出三个四位数的质数，能够形成等差数列,且差值为3330，并且能够互为排列。
%这要的质数组有两组。找出第二组
%使用传统的三重循环
% 此代码使用matlab编程
% Problem49所用时间为10.2873秒
% Problem49的答案为
%% Problem49.m
%最后编辑时间：2017-06-14 11:13 版本1.0
%找出三个四位数的质数，能够形成等差数列,且差值为3330，并且能够互为排列。
%这要的质数组有两组。找出第二组
%使用传统的三重循环
% 此代码使用matlab编程
% Problem49所用时间为10.2873秒
% Problem49的答案为
function Output = Problem49()
tic
%先刷出大于1000 小于10000 的素数组
Limit = 10000;
Judge = ones(1,Limit-1);
Judge(1) = 0;
for ii = 1:Limit-1
if Judge(ii) == 1
for jj = 2*ii : ii : Limit-1
Judge(jj) = 0;
end
end
end
PossiFactor = find(Judge == 1);
All = PossiFactor(PossiFactor > 1000);
Num = length(All);
Output = P49(Num,All);
toc
disp('此代码使用matlab编程')
disp(['Problem49所用时间为',num2str(toc),'秒'])
disp(['Problem49的答案为',mat2str(Output)])
end
% 此程序为了解决欧拉计划的第十九题
% 破除三重循环，使用return
function Output = P49(Num,All)
Output = zeros(2,3);
Time = 0;
for ii = 1 : Num-2
for jj = ii+1 : Num -1
for kk = jj+1 : Num
if All(jj) - 3330 == All(ii) && All(kk) - 3330 == All(jj)
if strcmp(sort(num2str(All(ii))),sort(num2str(All(kk)))) == 1 && ...%比较三个数是否为相互的排列数
strcmp(sort(num2str(All(ii))),sort(num2str(All(jj)))) == 1
Time = Time + 1;
Output(Time,:) = ;
if Time == 2
return
end
end
end
end
end
end
end 用的matlab
结果是:
296962999629
时间已过 0.028753 秒。
>> def isPrime(num):
if num <= 1:
return False
else:
for i in range(2, int(num**0.5+1)):
if num % i == 0:
return False
else:
return True
def numList(num):
numTemp = []
for i in range(int(len(str(num)))):
numTemp.append(int(str(num)))
numTemp.sort()
return list(set(numTemp))
#大于2的数为质数，其必然为奇数且为某4个数字的3种排列，所以最小为num1=1235
#所以递增的数i必然为偶数，且最大取到(9999-num1)/2
sequenceList = []
for num1 in range(1235, 9996, 2):
for i in range(2, (9999-num1)//2+1, 2):
if isPrime(num1):
num2 = num1 + i
if isPrime(num2):
num3 = num1 + 2*i
if isPrime(num3):
if numList(num1) == numList(num2) and numList(num1) == numList(num3):
sequenceList.append((num1, num2, num3))
#print(sequenceList)
numStr = ""
for each in sequenceList[-1]:
numStr += str(each)
print(int(numStr))
296962999629
符合队列：1487--4817--8147
符合队列：2969--6299--9629
用时:0.12480079999999999 秒
import itertools
import time
def is_prime(min_range, max_range):
bool_range = * max_range
bool_range, bool_range = 0, 0
for i, j in enumerate(bool_range):
if j:
for k in range(i**2, max_range, i):
bool_range = 0
return
def cal_result():
t_primes = is_prime(1000, 10000)
s_primes = set(t_primes)
for each_num in t_primes:
tmp_result = []
for each_str in itertools.permutations(str(each_num)):
tmp_num = int(''.join(each_str))
if tmp_num in s_primes:
tmp_result.append(tmp_num)
s_primes.remove(tmp_num)
tmp_result.sort()
if len(tmp_result) >= 3:
for i in range(len(tmp_result) - 2):
for j in range(i + 2, len(tmp_result)):
if (tmp_result + tmp_result)/2 in tmp_result:
print("符合队列：{}--{}--{}".format(tmp_result, int((tmp_result + tmp_result)/2), tmp_result))
if __name__ == "__main__":
cal_result()
print("用时:{} 秒".format(time.process_time())) 148748178147
296962999629
Process returned 0 (0x0) execution time : 0.025 s
Press any key to continue.
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M = 1e4;
int cnt = 0;
bool prime;
int factor;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
void parse(int a[],int x){
for (int i = 0;i < 4;i++){
a = x % 10;
x /= 10;
}
}
bool judge(int a[]){
bool b1 = false,b2 = false;
int t;
for (int i = 0;i < 4;i++) t = a;//反序，以下只需一论排列
do{
if (memcmp(t,a,sizeof(t) ) == 0) b1 = true;
if (memcmp(t,a,sizeof(t) ) == 0) b2 = true;
}while(next_permutation(t,t+4) );
return b1 && b2;
}
int main(){
euler_sieve();
int n = {0};
for (int j = 1000;j+6660 < 10000;j++){
n = j;
for (int i = 1;i < 3;i++) n = n + i*3330;
int a;
if (!prime ] || !prime ] || !prime ]) continue;
for (int i = 0;i < 3;i++) parse(a,n);
if (judge(a)) cout << n << n << n << endl;
}
return 0;
}
list1 = []#存放1000-10000的所有质数
def prime(n):
if n%2==0:
return False
else:
for i in range(3,int(n**0.5)+1,2):
if n%i==0:
return False
else:
return True
for i in range(1000,10001):
if prime(i):
list1.append(i)
def bj(a,b):
a = list(str(a))
a.sort()
b = list(str(b))
b.sort()
if a == b:
return True
list2 = []
for i in range(len(list1)):
for j in range(1,i):
s = list1 - list1
if bj(list1,list1):
if (list1+s) in list1:
if bj(list1,list1+s):
list2.append((list1,list1,list1+s))
print(list2) #include <stdio.h>
#include <math.h>
int check_prime(int);
int check_prime(int num)//判质数
{
int i, j;
j = sqrt(num + 1);
for (i = 2; i <= j; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
main()
{
int i, j, k, m, n, p;
for (i = 1489; i < 10000; i += 2)
{
int a = { 0 };
if (check_prime(i))
{
j = i + 3330;
n = i;
for (m = 0; m < 4; m++)//标记法，将i中各个位上的数用数组a标记
{
p = n % 10;
a = 1;
n /= 10;
}
n = j;
for (m = 0; m < 4; m++)//判断加3330后是否是第一个数的排列
{
p = n % 10;
if (a == 0)
{
goto Label;//不是就直接到标签Label处开始下一轮循环
}
n /= 10;
}
if (check_prime(j))
{
k = j + 3330;
n = k;
for (m = 0; m < 4; m++)//判断再加3330后是否是第一个数的排列
{
p = n % 10;
if (a == 0)
{
goto Label;
}
n /= 10;
}
if (check_prime(k))
{
printf("%d %d %d\n", i, j, k);
break;
}
}
}
Label:continue;
}
}
2969 6299 9629 #找出由互为排列的4位数质数组成的序列
from time import *
from math import *
from itertools import * #permutations(, 4)
#验证是否是质数
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 creat_increase(num):
if is_prime(num):
a = num
b = num + 3330
c = b + 3330
if is_prime(b) and is_prime(c):
return
else:
return None
else:
return None
#判断是否满足排列条件
def contidion(seq):
out_0 = 0
out_1 = 0
out_2 = 0
out_list0 = []
out_list1 = []
out_list2 = []
for i in str(seq):
out_0 += int(i)
out_list0.append(i)
out_list0.sort()
for i in str(seq):
out_1 += int(i)
out_list1.append(i)
out_list1.sort()
for i in str(seq):
out_2 += int(i)
out_list2.append(i)
out_list2.sort()
if out_0 == out_1 == out_2 and\
out_list0 == out_list1 == out_list2:
return True
#生成相差3330且3个数都是质数的序列列表
def creat_list():
num = 1000
total_list = []
while num + 6660 < 9999:
if creat_increase(num):
total_list.append(creat_increase(num))
num += 1
return total_list
s = time()
for each in creat_list():
if contidion(each):
print(each)
e = time()
print("用时%.4f秒" % (e-s))
#'''
/*
答案：296962999629
耗时：0.0170646秒
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
char cp;//素数表
int main(void)
{
//建立素数表
memset(cp, 1, 9998 * sizeof(char));
for (int i = 2; i <= 100; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j < 10000; j += i)
cp = 0;
}
char str = "";
for (int i = 1000; i < 10000; ++i)//枚举第一个素数
{
if (cp == 0 || i == 1487)
continue;
char str1 = "";
_itoa(i, str1, 10);
sort(str1, str1 + 4);
bool bFind = false;
for (int j = i + 1; j < 10000; ++j)//枚举第二个素数
{
if (cp == 0)
continue;
char str2 = "";
_itoa(j, str2, 10);
sort(str2, str2 + 4);
if (strcmp(str1, str2) != 0)//比对各位数字是否是排列
continue;
int nD = j - i;//计算公差
if (j + nD >= 10000)
continue;
if (cp == 1)//找到第三个候选数
{
char str3 = "";
_itoa(j + nD, str3, 10);
sort(str3, str3 + 4);
if (strcmp(str1, str3) != 0)//比对各位数字是否是排列
continue;
//找到了
bFind = true;
//拼接数字
_itoa(i, str1, 10);
strcat(str, str1);
_itoa(j, str2, 10);
strcat(str, str2);
_itoa(j + nD, str3, 10);
strcat(str, str3);
break;
}
}
if (bFind)
break;
}
cout << str << endl;
return 0;
}
import time as t
import math
from itertools import permutations
start = t.perf_counter()
def check_prime(a_num):
is_prime = 1
for i in range(2, int(math.sqrt(a_num) + 1)):
if a_num % i == 0:
is_prime = 0
return is_prime
bool_prime = * 10000
for pre in range(1000):
bool_prime = False
for num in range(1000, 10000):
if not check_prime(num):
bool_prime = False
for j in range(1000, 10000):
if bool_prime:
j_perm = set(permutations(str(j)))
bool_prime = False
nums =
count = 1
for k in j_perm:
k_str = ''
for m in k:
k_str += str(m)
k_int = int(k_str)
if bool_prime:
count += 1
bool_prime = False
nums.append(k_int)
nums.sort()
if count >= 3:
for n in nums:
if n + 6660 > 10000:
break
elif n + 3330 in nums and n + 6660 in nums:
print(n, n + 3330, n + 6660)
print("It costs %f s" % (t.perf_counter() - start))
1487 4817 8147
2969 6299 9629
It costs 0.042802 s
页:
[1]