#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

char s[60000], *p = s;
int prime[] = {3,5,7,11,13,17,19,23,29};

bool Miller_Rabin(unsigned n)
{
   unsigned k, p, q, t;
   unsigned long long a;
   for (q = 0, p = n-1; p % 2 == 0; p /= 2, ++q);
   for (k = 1, t = p; t /= 2; k *= 2);
   for (int times = 2; times; --times)
   {
       unsigned i = rand() % (n-2) + 2;
       for (a = i % n, t = k; t /= 2; )
       {
           a = a * a % n;
           if (t & p) a = a * i % n;
       }
       if (a == 1) continue;
       for (i = q; i; --i)
       {
           unsigned long long b = a * a % n;
           if (b == 1)
           {
               if (a == n-1) goto L1;
               return false;
           }
           a = b;
       }
       if (a != 1) return false;
L1:;
   }
   return true;
}

int main()
{
   unsigned cnt = 25, prev = 25;
   printf("2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97");
   for (unsigned bit = 2, k = 10; bit <= 5; ++bit, k *= 10)
   {
       for (unsigned front = 1; front <= 9; front += 2)
       {
           for (unsigned rear = 0; rear < k; ++rear)
           {
               unsigned t = front * k + rear, n = t, i = bit - 1;
               do n = n * 10 + (t /= 10) % 10;
               while (--i);
               for (int i = 0; i < sizeof(prime) / sizeof(prime[0]); ++i)
                   if (n % prime == 0) goto L1;
               if (!Miller_Rabin(n)) goto L1;
               ++cnt;
               *p++ = ' ';
               {
                   char *first = p, *last;
                   for (int t = n; t; *p++ = t%10+'0', t /= 10);
                   for (last = p; first < --last; swap(*first++, *last));
               }
L1:;
           }
       }
   }
   *p = '\0';
   puts(s);
   printf("\nTotal: %u\nTime: %f\n", cnt, (double)clock() / CLK_TCK);
   getchar();
   return 0;
}


Disclaimer: some contents on this website are collected through internet etc. Please notify if violated the original author's copyright and we will delete it immediately.
免责声明：本站部分文章来源于网络等其它媒体，如果侵犯了原作者的版权，请联系我们，本站将立即删除。