nsz Git - libfirm/blob - ir/be/test/biggest_prime.c

   1 #include <stdio.h>
   2
   3 static int m = 754974721;
   4 static int N;
   5 static int t[1 << 22];
   6 static int a;
   7 static int *p;
   8 static int i;
   9 //static int e = 1 << 22;
  10 static int e = 1 << 10;
  11 static int j;
  12 static int s;
  13 static int b;
  14 static int c;
  15 static int U;
  16
  17 void f(int d)
  18 {
  19         for (s = 1 << 23; s; s /= 2, d = d * 1L * d % m) {
  20                 if (s >= N) continue;
  21                 for (p = t; p < t + N; p += s) {
  22                         for (i = s, c = 1; i; i--) {
  23                                 b = *p + p[s], p[s] = (m + *p - p[s]) *
  24                                         1L * c % m, *p++ = b % m, c = c * 1L * d % m;
  25                         }
  26                 }
  27         }
  28
  29         for (j = 0; i < N - 1;)
  30         {
  31                 for (s = N / 2; !((j ^= s) & s); s /= 2)
  32                 {}
  33
  34                 if (++i < j)
  35                         a = t[i], t[i] = t[j], t[j] = a;
  36         }
  37 }
  38
  39 int main ()
  40 {
  41         *t = 2;
  42         U = N = 1;
  43
  44         while (e /= 2) {
  45                 N *= 2;
  46                 U = U * 1L * (m + 1) / 2 % m;
  47                 f(362);
  48                 for (p = t; p < t + N;)
  49                         *p++ = (*p * 1L * *p % m) * U % m;
  50
  51                 f(415027540);
  52                 for (a = 0, p = t; p < t + N;) {
  53                         a += (0x6A64B1 & e ? 2 : 1) * *p;
  54                         *p++ = a % 10;
  55                         a /= 10;
  56                 }
  57         }
  58
  59         while (!*--p)
  60                 ;
  61
  62         t[0]--;
  63         {
  64                 int qs = 0;
  65                 while (p >= t)
  66                         qs += *p--;
  67                 printf ("Checksumme = %d\n", qs);
  68         }
  69         return 0;
  70 }