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

欧拉计划

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)[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]

芒果加黄桃

# 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

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

渡风

此代码使用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

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饭

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

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)

王小召

结果是：[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()))

永恒的蓝色梦想

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

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

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))

   
        

有马_冬巳

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

#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

/*
答案：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

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

运行结果

$ 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}");
            }
        }
    }
}