• Source
    1. #include<bits/stdc++.h>
    2. #define MAX 1000005
    3. #define pb push_back
    4.  
    5. using namespace std;
    6.  
    7. vector<int>prime;
    8.  
    9. bool check[MAX];
    10.  
    11. int ans[MAX];
    12.  
    13. void sieve()
    14. {
    15. int i,j,k;
    16.  
    17. k = sqrt(MAX);
    18.  
    19. for(i=3; i<=k; i+=2)
    20. {
    21. if(check[i]==0)
    22. {
    23. for(j=i*i; j<MAX; j+=i+i)
    24. {
    25. check[j]=1;
    26. }
    27. }
    28. }
    29.  
    30. for(i=101; i<=999999; i+=2)
    31. {
    32. if(!check[i])
    33. {
    34. prime.pb(i);
    35. }
    36. }
    37. }
    38.  
    39. void solve()
    40. {
    41. int len = prime.size();
    42.  
    43. string s;
    44.  
    45. char ch,str[10];
    46.  
    47. int i,j,num,lenS,cnt,crclr_prime;
    48.  
    49. for(i=0; i<len; i++)
    50. {
    51. sprintf(str,"%d",prime[i]);
    52.  
    53. s = string(str);
    54.  
    55. lenS = s.length();
    56.  
    57. bool tag = false;
    58.  
    59. for(j=0;j<lenS;j++)
    60. {
    61. if(s[j]=='0'||s[j]=='2'||s[j]=='4'||s[j]=='6'||s[j]=='8')
    62. {
    63. tag = true;
    64.  
    65. break;
    66. }
    67. }
    68.  
    69. if(tag)
    70. continue;
    71.  
    72. crclr_prime = cnt = 0;
    73.  
    74. while(cnt<lenS-1)
    75. {
    76. ch = s[0];
    77.  
    78. s.erase(s.begin());
    79.  
    80. s.insert(s.begin()+lenS-1,ch);
    81.  
    82. cnt++;
    83.  
    84. num = atoi(s.c_str());
    85.  
    86. if(!check[num])
    87. {
    88. crclr_prime++;
    89. }
    90. }
    91.  
    92. if(crclr_prime==lenS-1)
    93. {
    94. ans[prime[i]] = 1;
    95. }
    96. }
    97.  
    98. for(i=101; i<=MAX-5; i++)
    99. {
    100. ans[i]+=ans[i-1];
    101. }
    102. }
    103.  
    104. int main()
    105. {
    106. sieve();
    107.  
    108. solve();
    109.  
    110. int from,to,res;
    111.  
    112. while(scanf("%d",&from)==1)
    113. {
    114. if(from==-1)
    115. {
    116. break;
    117. }
    118.  
    119. scanf("%d",&to);
    120.  
    121. res = ans[to]-ans[from-1];
    122.  
    123. if(res==0)
    124. {
    125. puts("No Circular Primes.");
    126.  
    127. continue;
    128. }
    129.  
    130. (res==1) ? printf("%d Circular Prime.\n",res) :
    131.  
    132. printf("%d Circular Primes.\n",res);
    133.  
    134. }
    135.  
    136. return 0;
    137. }