Problem 37 Truncatable primes （暴力）

素颜马尾好姑娘i 2022-07-15 02:26 86阅读 0赞

## Truncatable primes ##

### Problem 37 ###

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.

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td> 
        <div style="text-align:right"> 
         <span style="font-size:18px">Answer:</span> 
        </div> </td> 
       <td><strong><span style="font-size:18px">748317</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Sat, 29 Oct 2016, 15:27</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    int is_prime(int n)
    {
        if(n <= 1) return 0;
        if(n == 2 || n == 3) return 1;
        else if (n % 2 == 0) return 0;
        else
        {
            for(int i=3;i<(int)sqrt((float)n)+1;i++)
            {
                if(n % i == 0) return 0;
            }
        }
        return 1;
    }
    int truncatable(int n) //左移右移后是否是素数 
    {
        if (n<=0) return 0;
     
        //n的长度
        int len = 0;
        int cpy = n;
        while (cpy !=0) 
        {
            len ++;
            cpy /= 10;
        }
        //右移
        cpy = n;
        while (cpy !=0)
        {
            if(!is_prime(cpy)) 
            {
                return 0;
            }
            cpy /= 10;           
        }
        //左移
        cpy = n;
        while(len>1)
        {
            int x = cpy % (int)pow((float)10,len-1); //低位取模
            if (!is_prime(x))
            {
                return 0;
            }
            len--;
        }
     
        return 1;
    }
     
    int main()
    {
        int cnt = 0,sum=0,i=8;
        while(cnt< 11)
        {
            if (truncatable(i))
            {
                sum += i;
                cnt ++;
                cout<<i<<endl;
            }
            i++;
        }
        cout<<endl;
        cout<<"sum="<<sum<<endl;
        return 0;
    }