题目37：找出所有11个可以双向裁剪的质数的和
本帖最后由 永恒的蓝色梦想 于 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 不被认为是可裁剪的质数。 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;
} 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))
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))):
tmp = False
break
if tmp :
if each not in list3:
list3.append(each)
print(list3)
跑到10W就找到10个
# encoding:utf-8
# 寻找100万以下的十进制和二进制都是回文数的数之和
from time import time
def getPrimes(N=1000000):
l_result = * N
l_result, l_result = False, False
for i in range(0, N):
if l_result:
for j in range(i * i, N, i):
l_result = False
return
def euler037():
l_primes = getPrimes()
l_result = []
for each in l_primes:
if len(str(each)) >= 2:
if str(each) in ('4', '6', '8', '9'):
continue
if (str(each)[::-1]) 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
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))
效率比较低，要30-40s 本帖最后由 永恒的蓝色梦想 于 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)
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))
748317 此代码使用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 from time import time
start = time()
def judgePrime(n):
if n == 1:
return False
for iin 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
test_list.append(int(result_str))
result_str = test_str
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! from time import time
def tailor(num):
temp = str(num)
for i in range(1,len(temp)):
temp = temp
yield int(temp)
temp = str(num)
for j in range(1,len(temp)):
temp =temp[:-1]
yield int(temp)
def prime():
a,temp = 5,
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 =
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:
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
本帖最后由 永恒的蓝色梦想 于 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)))
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)
结果是：
用时：0.5460035 秒
import time
def prime_list(num_range):
bool_num = * (num_range+1)
bool_num = 0
bool_num = 0
for i, j in enumerate(bool_num):
if j:
for x in range(i**2, num_range+1, i):
bool_num = 0
return bool_num
def get_result():
result = []
count = 0
num_index = 10
prime_lists = prime_list(1000000)
while count != 11:
if prime_lists:
mark = 1
for i in range(1, len(str(num_index))):
if not prime_lists)] or not prime_lists)]:
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-5-2 16:56 编辑
C++ 25ms#define max 1000000
#include<iostream>
using namespace std;
int arr;
bool judge(int d) {
int temp = d, p = 1;
while (temp /= 10) {
if (arr) {
return false;
}
}
while (d) {
temp += (d % 10) * p;
p *= 10;
d /= 10;
if (arr) {
return false;
}
}
return true;
}
int main() {
int i, j, k, count = 11, sum = 0;
arr = arr = 1;
for (j = 4; j < max; j += 2) {
arr = 1;
}
for (i = 3; i < 10; i += 2) {
if (!arr) {
for (j = i << 1; j < max; j += i) {
arr = 1;
}
}
}
for (i = 11; i < max && count; i += 2) {
if (!arr) {
if (judge(i)) {
sum += i;
count--;
}
k = i << 1;
for (j = k + i; j < max; j += k) {
arr = 1;
}
}
}
cout << sum << endl;
return 0;
} 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;
int factor;
const int il[] = {0,4,6,8};
deque<int> v;
int n;
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;
}
}
}
bool illegal(){
for (int i = 0;i < v.size();i++)
for (int j = 0;j < 4;j++)
if (v == il) return true;
return false;
}
void prt(){
for (int i = 0;i < v.size();i++)
cout << v << " ";
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 * times;//自右向左
//cout << t << endl;
if (!prime){trun = false;break;}
times *= 10;
}
t = 0;
for (int j = 0;j < sz;j++){
t *= 10;t += v;//自左向右
if (!prime){trun = false;break;}
}
if (trun) {cnt++; sum += i;
//cout << i << endl;
}
if (cnt == 11)break;
}
cout << sum << endl;
return 0;
}
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))
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))
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:
each = str(each)
check = 0
for i in range(len(each) - 1):
if int(each) not in primes or int(each) not in primes:
check += 1
if check == 0:
fancyprimes.append(int(each))
print(fancyprimes)
end = time.time()
print("共用时%f秒" %(end - start))
共用时0.097235秒 #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;
int i, len;
sprintf(str, "%d", num);
len = strlen(str);
for (i = 0; i < len; i++)
{
a = str - '0';
}
}
main()
{
char str;
int i, j, k, m, len, flag = 1;
int n = 11, count = 0, a;
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 * pow(10, i);
if (check_num(j) == 0)
{
flag = 0;
break;
}
}
if (flag)
{
j = 0;
for (i = 0; i < len - 1; i++)//从右边边截去
{
j += a;
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 /*
答案：748317
耗时：0.006687秒
*/
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1000000;
char cp;
vector<int> vp;
int main(void)
{
//筛法打素数表
memset(cp + 2, 1, (N + 2) * sizeof(char));
for (int i = 2; i <= 1000; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j <= N; j += i)
cp = 0;
}
vp.push_back(2);
for (int i = 3; i <= N; i += 2)
{
if (cp == 1)
vp.push_back(i);
}
int k = 4, nCount = 0, nSum = 0, nV = (int)vp.size();
while (nCount < 11 && k < nV)
{
int p = vp;//对素数逐个检查
char str_p;
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 == 0)//检查是否是素数
{
bFlag = false;
break;
}
}
if (bFlag)
{
//再从右向左检查
for (int i = nLen - 1; i >= 1; --i)
{
str_p = 0;//逐个截掉最右边的数字
int a = atoi(str_p);
if (cp == 0)//检查是否是素数
{
bFlag = false;
break;
}
}
if (bFlag)//这个数满足要求
{
nSum += p;//累加值
++nCount;//累加计数
}
}
}
printf_s("%d\n", nSum);
return 0;
} 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 = * 1000000
bool_prime, bool_prime = False, False
for i in range(1000000):
is_truncatable = True
if bool_prime:
if check_prime(i):
i_range = int(math.log10(i))
for j in range(1, i_range + 1):
if not bool_prime or not bool_prime:
is_truncatable = False
break
if is_truncatable and i > 10:
truncatable_primes.append(i)
if len(truncatable_primes) == 11:
break
else:
bool_prime = False
for k in range(i * 2, 1000000 - 1, i):
bool_prime = False
print(truncatable_primes)
print(sum(truncatable_primes))
print("It costs %f s" % (t.perf_counter() - start))
748317
It costs 1.696134 s 运行结果
$ 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!;
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}");
}
}
}
}
页:
[1]