题目35：100万以下有多少个循环质数？

mathtimes

1. #include <vector>
   
2. #include <cmath>
   
3. #include <iostream>
   
4. using namespace std;
   
5. bool similar(int x,int y,int len)
   
6. {
   
7.     if(len==1)
   
8.         return false;
   
9.     char bits1[len]{0};
   
10.     char bits2[len]{0};
    
11.     int i = 0;
    
12.     while(x>0)
    
13.     {
    
14.         bits1[i++] = x%10;
    
15.         x /= 10;
    
16.     }
    
17.     i = 0;
    
18.     while(y>0)
    
19.     {
    
20.         bits2[i++] = y%10;
    
21.         y /= 10;
    
22.     }
    
23.     i = 0;
    
24.     while(++i<len)
    
25.     {
    
26.         for(int j=0;j<len-1;j++)
    
27.             swap(bits1[j],bits1[j+1]);
    
28.         for(int j=0;j<len;j++)
    
29.             if(bits1[j]!=bits2[j])
    
30.                 goto continuetodo;
    
31.         return true;
    
32.         continuetodo:;
    
33.     }
    
34.     return false;
    
35. }
    
36. int main()
    
37. {
    
38.     vector<int> prime,count;
    
39.     prime.reserve(73000);
    
40.     count.reserve(73000);
    
41.     prime.push_back(2);
    
42.     count.push_back(1);
    
43.     int i = 3;
    
44.     while(i<(int)1e6)
    
45.     {
    
46.         bool s = true;
    
47.         for(auto j=prime.begin();*j<=sqrt(i)&&j!=prime.end();j++)
    
48.             if(i%*j==0)
    
49.             {   
    
50.                 s = false;
    
51.                 break;
    
52.             }
    
53.         if(s)
    
54.         {
    
55.             prime.push_back(i);
    
56.             count.push_back(1);
    
57.             int t = prime.size()-1;
    
58.             int len = (int)log10(prime[t]);
    
59.             if(similar(i,i,len+1))
    
60.                 count.back() = -1;
    
61.             int floornum = pow(10,len);
    
62.             while(prime[--t]>floornum)
    
63.                 if(similar(i,prime[t],len+1))
    
64.                 {
    
65.                     count.back() += count[t];
    
66.                     break;
    
67.                 }
    
68.         }
    
69.         i += 2;
    
70.     }
    
71.     i = prime.size();
    
72.     int sum = 0;
    
73.     for(int j=0;j<i;j++)
    
74.     {
    
75.         if(count[j]==-1)
    
76.             sum ++;
    
77.         if(count[j]==(int)log10(prime[j])+1)
    
78.             sum += count[j];
    
79.     }
    
80.     cout<<sum;
    
81. }

复制代码