题目37：找出所有11个可以双向裁剪的质数的和

欧拉计划 · 发表于 2015-4-24 00:37:49

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由永恒的蓝色梦想于 2020-6-16 12:30 编辑

Truncatable primes

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

题目：

3797 这个数很有趣。它本身是质数，而且如果我们从左边不断地裁去数字，得到的仍然都是质数：3797, 797, 97, 7。而且我们还可以从右向左裁剪：3797, 379, 37, 3，得到的仍然都是质数。

找出全部 11 个这样从左向右和从右向左都可以裁剪的质数的和。

注意：2, 3, 5 和 7 不被认为是可裁剪的质数。

迷雾少年 · 发表于 2016-8-30 12:08:56

3
5
7
31
37
53
59
71
73
79
311
313
317
373
379
593
599
719
733
739
797
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
请按任意键继续. . .

#include <iostream>
using namespace std;
bool iszhishu(int n)
{
if(1==n || 2==n)
return false;
for (int z = 2;z*z<=n;z++)
{
if(n%z==0)
return false;
}
return true;
}
bool is(int n)
{
/* 从又开始裁剪 */
int h=0;
int k = n;
if(!iszhishu(n)) return false;
while ( k )
{
k/=10; //裁剪
if( iszhishu(k) )
continue;
else return false;
h++;
}
/* 从左开始裁剪 */
k=n;
int i = 1;
while ( h )
{
//不是质数
if(!iszhishu(n%(int)pow(10,i++)))
return false;
h--;
}
return true;
}
int main(void)
{
for (int n = 2;n<=10000;n++)
{
if(is(n))
{
std::cout<<n<<endl;
}
}
return 0;
}

复制代码

愤怒的大头菇 · 发表于 2016-9-6 11:03:25

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
list2 = []
list3 = []
for i in range(100000):
if prime(i):
if len(str(i)) > 1:
temp = True
list1 = []
for j in range(len(str(i))-1):
list1.append(str(i)[j+1:])
for each in list1:
if not prime(int(each)):
temp = False
break
if temp:
list2.append(i)
for each in list2:
tmp = True
for n in range(len(str(each))):
if not prime(int(str(each)[0:n+1])):
tmp = False
break
if tmp :
if each not in list3:
list3.append(each)
print(list3)

复制代码

跑到10W就找到10个
[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797]

芒果加黄桃 · 发表于 2017-1-14 13:53:27

# encoding:utf-8
# 寻找100万以下的十进制和二进制都是回文数的数之和
from time import time
def getPrimes(N=1000000):
l_result = [True] * N
l_result[0], l_result[1] = False, False
for i in range(0, N):
if l_result[i]:
for j in range(i * i, N, i):
l_result[j] = False
return [k for (k, v) in enumerate(l_result) if v]
def euler037():
l_primes = getPrimes()
l_result = []
for each in l_primes:
if len(str(each)) >= 2:
if str(each)[0] in ('4', '6', '8', '9'):
continue
if (str(each)[::-1])[0] in ('6', '9'):
continue
flag = True
for i in range(1, len(str(each))):
t1 = each % 10 ** i
t2 = each // 10 ** i
if not(t1 in l_primes) or not(t2 in l_primes):
flag = False
break
if flag:
l_result.append(each)
print(l_result)
if len(l_result) == 11:
break
def euler037_1():
l_primes = getPrimes()
l_result = []
for each in l_primes:
tmp = str(each)
if len(tmp) >= 2:
if tmp.startswith('4') or tmp.startswith('6') or tmp.startswith('8') or tmp.startswith('9') or tmp.endswith('6') or tmp.endswith('9'):
continue
flag = True
for i in range(1, len(tmp)):
t1 = tmp[i:]
t2 = tmp[:len(tmp) - i]
if not(int(t1) in l_primes) or not(int(t2) in l_primes):
flag = False
break
if flag:
l_result.append(each)
if len(l_result) == 11:
print(l_result)
break
if __name__ == '__main__':
start = time()
euler037_1()
print('cost %.6f sec' % (time() - start))

复制代码

[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
效率比较低，要30-40s

pan1990 · 发表于 2017-4-19 10:02:15

本帖最后由永恒的蓝色梦想于 2020-7-2 18:36 编辑

from math import sqrt
def is_prime(n):
if n==1:
return False
for i in range(2,int(sqrt(n)+1)):
if n%i==0:
return False
return True
def right_number(n):
list1=[]
n=str(n)
for i in range(len(n)):
list1.append(n[i:])
return list1
def left_number(n):
list1=[]
n=str(n)
for i in range(1,len(n)):
list1.append(n[-(len(n)):-i])
return list1
number=9
count=1
list2=[]
while count<=11:
if is_prime(number):
Judge=True
right_n=right_number(number)
left_n=left_number(number)
for n in right_n:
if not is_prime(int(n)):
Judge=False
break
for n in left_n:
if not is_prime(int(n)):
Judge=False
break
if Judge:
list2.append(number)
#print(number)
count+=1
number+=1
print(sum(list2))

复制代码

[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
748317

渡风 · 发表于 2017-6-14 22:51:23

此代码使用matlab编程
Problem37所用时间为： 14.9352秒
Problem37的答案为： 748317

%% Problem37.m
% 最后编辑时间：17-06-14 22:34
% 找出11个双向裁剪质数的和
% Problem37所用时间为： 14.9352秒
% Problem37的答案为： 748317
function Output = Problem37()
tic
Limit = 1000000;
Vector = GetPrime(Limit);
Vector = Vector(5:end);
N = length(Vector);
Output = 0;
Time = 0;
for ii = 1:N
Judge = 1;
L = length(num2str(Vector(ii)));
for jj = 1:L-1
if isprime(floor(Vector(ii)/(10^jj))) == 0
Judge = 0;
break
end
end
if Judge == 1
Str = num2str(Vector(ii));
for jj = 2:L
if isprime(str2double(Str(jj:L))) == 0
Judge = 0;
break
end
end
end
if Judge == 1
Output = Output + Vector(ii);
Time = Time + 1;
disp(Vector(ii))
if Time == 11
break
end
end
end
toc
disp('此代码使用matlab编程')
disp(['Problem37所用时间为： ',num2str(toc),'秒'])
disp(['Problem37的答案为： ',num2str(Output)])
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

复制代码

zengtaozt · 发表于 2017-8-12 13:27:06

from time import time
start = time()
def judgePrime(n):
if n == 1:
return False
for i in range(2,int(n**0.5)+1):
if n % i == 0 and n != 2:
return False
return True
def getNumber(n):
test_list = []
test_str = str(n)
for i in range(0,len(test_str)):
result_str = test_str[i:]
test_list.append(int(result_str))
result_str = test_str[0:len(test_str)-i]
test_list.append(int(result_str))
return set(test_list)
if __name__ == "__main__":
list = []
count = 1
number = 11
while count<= 11:
if judgePrime(number):
for each in getNumber(number):
if not judgePrime(each):
break
else:
count +=1
list.append(number)
number +=1
print(sum(set(list)))
print("Program running cost %4f secs!"%(time()-start))

复制代码

748317
Program running cost 6.923396 secs!

JAY饭 · 发表于 2018-11-7 05:07:50

from time import time
def tailor(num):
temp = str(num)
for i in range(1,len(temp)):
temp = temp[1:]
yield int(temp)
temp = str(num)
for j in range(1,len(temp)):
temp =temp[:-1]
yield int(temp)
def prime():
a,temp = 5,[2,3]
while True:
for k in temp:
if a%k == 0:
break
elif k*k > a:
temp.append(a)
yield a
break
a += 2
def prime2():
temp = [False,False,2,3]
a,begin = 0,3
for k in prime():
for l in range(begin+1,k):
temp.append(False)
temp.append(k)
begin = k
T = True
if k > 10:
for n in tailor(k):
if not temp[n]:
T = False
break
if T:
a += 1
print(k)
if a == 11:
return True
start = time()
prime2()
print('cost %.2fs'%(time()-start))

复制代码

11个数 2.23S

k往事如烟k · 发表于 2019-3-28 11:31:58

本帖最后由永恒的蓝色梦想于 2020-7-2 18:37 编辑

def isPrime(num):
if num <= 1:
return False
i = 2
while i * i <= num:
if num % i == 0:
return False
i += 1
return True
def isTruncatablePrime(num):
str1 = str(num)
length = len(str1)
if isPrime(num):
boolTemp = []
for i in range(length):
boolTemp.append(isPrime(int(str1[i:])))
boolTemp.append(isPrime(int(str1[:length-i])))
if False in boolTemp:
return False
else:
return True
else:
return False
TruncatablePrimeNumList = []
for num in range(10, 1000000):
if isTruncatablePrime(num):
TruncatablePrimeNumList.append(num)
print(TruncatablePrimeNumList)

复制代码

王小召 · 发表于 2019-6-13 17:14:32

结果是：[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
用时：0.5460035 秒

import time
def prime_list(num_range):
bool_num = [1] * (num_range+1)
bool_num[0] = 0
bool_num[1] = 0
for i, j in enumerate(bool_num):
if j:
for x in range(i**2, num_range+1, i):
bool_num[x] = 0
return bool_num
def get_result():
result = []
count = 0
num_index = 10
prime_lists = prime_list(1000000)
while count != 11:
if prime_lists[num_index]:
mark = 1
for i in range(1, len(str(num_index))):
if not prime_lists[int(str(num_index)[i:])] or not prime_lists[int(str(num_index)[:-i])]:
mark = 0
break
if mark:
result.append(num_index)
count += 1
num_index += 1
return result
print("结果是：{}\n用时：{} 秒".format(get_result(), time.process_time()))

复制代码

永恒的蓝色梦想 · 发表于 2020-4-19 17:21:31

本帖最后由永恒的蓝色梦想于 2020-5-2 16:56 编辑

C++ 25ms

#define max 1000000
#include<iostream>
using namespace std;
int arr[max];
bool judge(int d) {
int temp = d, p = 1;
while (temp /= 10) {
if (arr[temp]) {
return false;
}
}
while (d) {
temp += (d % 10) * p;
p *= 10;
d /= 10;
if (arr[temp]) {
return false;
}
}
return true;
}
int main() {
int i, j, k, count = 11, sum = 0;
arr[0] = arr[1] = 1;
for (j = 4; j < max; j += 2) {
arr[j] = 1;
}
for (i = 3; i < 10; i += 2) {
if (!arr[i]) {
for (j = i << 1; j < max; j += i) {
arr[j] = 1;
}
}
}
for (i = 11; i < max && count; i += 2) {
if (!arr[i]) {
if (judge(i)) {
sum += i;
count--;
}
k = i << 1;
for (j = k + i; j < max; j += k) {
arr[j] = 1;
}
}
}
cout << sum << endl;
return 0;
}

复制代码

debuggerzh · 发表于 2020-8-12 17:18:56

748317

Process returned 0 (0x0) execution time : 0.450 s
Press any key to continue.
利用双端队列，实现数字到字串的转换，再分别从两个方向处理

#include<iostream>
#include<cmath>
#include<cstring>
#include<deque>
using namespace std;
const int M = 1e6;
int cnt = 0;
bool prime[M];
int factor[M];
const int il[] = {0,4,6,8};
deque<int> v;
int n;
void euler_sieve(){
prime[1] = false;
for (int i = 2;i <= M;i++) prime[i] = true;
for (int i = 2;i <= M;i++){
if (prime[i]) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor[j] < M;j++){
prime[i*factor[j]] = false;
if (i % factor[j] == 0) break;
}
}
}
bool illegal(){
for (int i = 0;i < v.size();i++)
for (int j = 0;j < 4;j++)
if (v[i] == il[j]) return true;
return false;
}
void prt(){
for (int i = 0;i < v.size();i++)
cout << v[i] << " ";
cout << endl;
}
bool parse(int x){
v.clear();
while(x){
v.push_front(x % 10);
x /= 10;
}
//prt();
if (illegal()) return true;
return false;
}
int main(){
euler_sieve();
int cnt = 0,sum = 0;
for (int i = 23; ;i++){
if (parse(i)) continue;
bool trun = true;
int t = 0,sz = v.size(),times = 1;
for (int j = sz-1;j >= 0;j--){
t += v[j] * times;//自右向左
//cout << t << endl;
if (!prime[t]) {trun = false; break;}
times *= 10;
}
t = 0;
for (int j = 0;j < sz;j++){
t *= 10; t += v[j];//自左向右
if (!prime[t]) {trun = false; break;}
}
if (trun) {cnt++; sum += i;
//cout << i << endl;
}
if (cnt == 11) break;
}
cout << sum << endl;
return 0;
}

复制代码

4444567 · 发表于 2020-10-5 11:09:47

from time import time
def prime(n):
if n<=1:
return False
elif n == 2 or n==3:
return True
else:
for i in range(2,int(n**0.5+1)):
if n%i==0:
return False
else:
return True
list1 = []
def zuo(n):
a = len(str(n))-1
while a:
n = int(str(n)[1:])
if prime(n):
a -= 1
else:
return False
if a==0:
return True
def you(n):
m = list(str(n))
a = len(m)-1
while a:
m.pop()
b = int(''.join(m))
if prime(b):
a -= 1
else:
return False
if a==0:
return True
t = time()
for i in range(10,1000000):
if '0' in str(i):
continue
else:
if prime(i):
if zuo(i):
if you(i):
list1.append(i)
print(list1,sum(list1))
print('cos %s' % (time()-t))

复制代码

有马_冬巳 · 发表于 2020-10-31 11:40:12

start = time.time()
a = 2
primes = []
fancyprimes = []
while a < 10000:
check = 0
for i in range(2,int(math.sqrt(a))+1):
if a % i == 0:
check += 1
if check == 0:
primes.append(a)
a += 1
for each in primes[4:]:
each = str(each)
check = 0
for i in range(len(each) - 1):
if int(each[0 : i+1]) not in primes or int(each[len(each)-1-i : len(each)]) not in primes:
check += 1
if check == 0:
fancyprimes.append(int(each))
print(fancyprimes)
end = time.time()
print("共用时%f秒" %(end - start))

复制代码

[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797]
共用时0.097235秒

a1351468657 · 发表于 2021-3-16 20:15:56

#include <stdio.h>
#include <string.h>
#include <math.h>
int check_num(int);
void split(int num, int a[]);
int check_num(int num) //判质数
{
if (num == 2)
{
return 1;
}
if (num == 1)
{
return 0;
}
int i, j, k;
k = num;
j = sqrt(num + 1);
for (i = 2; i <= j; i++)
{
if (k % i == 0)
{
return 0;
}
}
return 1;
}
void split(int num, int a[]) // 将数字各个位数存到a中
{
char str[20];
int i, len;
sprintf(str, "%d", num);
len = strlen(str);
for (i = 0; i < len; i++)
{
a[i] = str[i] - '0';
}
}
main()
{
char str[32];
int i, j, k, m, len, flag = 1;
int n = 11, count = 0, a[32];
while (1)
{
n += 2;
if (count == 11)
{
break;
}
if (check_num(n))
{
split(n, a);
sprintf(str, "%d", n);
len = strlen(str);
k = len - 1;
j = 0;
for (i = 0; i < len - 1; i++)//从左边截去
{
j += a[k--] * pow(10, i);
if (check_num(j) == 0)
{
flag = 0;
break;
}
}
if (flag)
{
j = 0;
for (i = 0; i < len - 1; i++)//从右边边截去
{
j += a[i];
if (check_num(j) == 0)
{
flag = 0;
break;
}
j *= 10;
}
}
if (flag)
{
count++;
printf("%d ", n);
}
}
flag = 1;
}
}

复制代码

秒出答案，判质数用欧拉筛法应该更快

答案：23 37 53 73 313 317 373 797 3137 3797 739397

guosl · 发表于 2022-1-3 17:42:01

/*
答案：748317
耗时：0.006687秒
*/
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1000000;
char cp[N + 4];
vector<int> vp;
int main(void)
{
//筛法打素数表
memset(cp + 2, 1, (N + 2) * sizeof(char));
for (int i = 2; i <= 1000; ++i)
{
if (cp[i] == 0)
continue;
for (int j = i * i; j <= N; j += i)
cp[j] = 0;
}
vp.push_back(2);
for (int i = 3; i <= N; i += 2)
{
if (cp[i] == 1)
vp.push_back(i);
}
int k = 4, nCount = 0, nSum = 0, nV = (int)vp.size();
while (nCount < 11 && k < nV)
{
int p = vp[k++];//对素数逐个检查
char str_p[12];
sprintf_s(str_p, "%d", p);
//先从左向右检查
int nLen = strlen(str_p);
bool bFlag = true;//这个数是否满足要求的标志
for (int i = 1; i < nLen; ++i)
{
int a = atoi(str_p + i);//逐个截掉最左边的数字
if (cp[a] == 0)//检查是否是素数
{
bFlag = false;
break;
}
}
if (bFlag)
{
//再从右向左检查
for (int i = nLen - 1; i >= 1; --i)
{
str_p[i] = 0;//逐个截掉最右边的数字
int a = atoi(str_p);
if (cp[a] == 0)//检查是否是素数
{
bFlag = false;
break;
}
}
if (bFlag)//这个数满足要求
{
nSum += p;//累加值
++nCount;//累加计数
}
}
}
printf_s("%d\n", nSum);
return 0;
}

复制代码

B1tetheDust · 发表于 2022-10-24 15:56:11

import time as t
import math
start = t.perf_counter()
def check_prime(a_num):
is_prime = True
for num_index in range(2, int(math.sqrt(a_num) + 1)):
if a_num % num_index == 0:
is_prime = False
return is_prime
truncatable_primes = []
bool_prime = [True] * 1000000
bool_prime[0], bool_prime[1] = False, False
for i in range(1000000):
is_truncatable = True
if bool_prime[i]:
if check_prime(i):
i_range = int(math.log10(i))
for j in range(1, i_range + 1):
if not bool_prime[i // 10 ** j] or not bool_prime[i % (10 ** j)]:
is_truncatable = False
break
if is_truncatable and i > 10:
truncatable_primes.append(i)
if len(truncatable_primes) == 11:
break
else:
bool_prime[i] = False
for k in range(i * 2, 1000000 - 1, i):
bool_prime[k] = False
print(truncatable_primes)
print(sum(truncatable_primes))
print("It costs %f s" % (t.perf_counter() - start))

复制代码

[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
748317
It costs 1.696134 s

mathtimes · 发表于 2023-10-15 18:28:30

运行结果

$ time target/release/main
23
53
73
37
313
373
317
797
3137
3797
739397
real 0m0.007s
user 0m0.007s
sys 0m0.000s

复制代码

题目结果

sum=0;for i in `target/release/main`; do((sum+=i));done;echo $sum
748317

复制代码

使用 primal 库，Miller-Rabin方法检测质数

use std::collections::HashSet;
use primal::*;
fn prime_r(x:u64) -> bool {
if x == 0 { return true;}
if ! is_prime(x) {return false;}
prime_r(x / 10)
}
fn main() {
let mut v = vec![2,3,5,7];
let mut bit = 1;
while ! v.is_empty() {
let mut r = Vec::new();
for i in v {
for j in 1..10 {
let x = i + j * 10u64.pow(bit);
if is_prime(x) {
r.push(x);
}
}
}
v = r;
bit += 1;
for i in &v {
if *i > 1e10 as u64 {
return ();
}
if prime_r(*i) {
println!("{i}");
}
}
}
}

复制代码

账号		自动登录	找回密码
密码			立即注册