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

   1 int m = 754974721, N, t[1 << 22], a, *p, i, e = 1 << 22, j, s, b, c, U;
   2
   3 f (d)
   4 {
   5         for (s = 1 << 23; s; s /= 2, d = d * 1L * d % m)
   6                 if (s < N)
   7                         for (p = t; p < t + N; p += s)
   8                                 for (i = s, c = 1; i; i--)
   9                                         b = *p + p[s], p[s] = (m + *p - p[s]) *
  10                                                 1L * c % m, *p++ = b % m, c = c * 1L * d % m;
  11
  12         for (j = 0; i < N - 1;)
  13         {
  14                 for (s = N / 2; !((j ^= s) & s); s /= 2)
  15                         ;
  16
  17                 if (++i < j)
  18                         a = t[i], t[i] = t[j], t[j] = a;
  19         }
  20 }
  21
  22 int main ()
  23 {
  24         *t = 2;
  25         U = N = 1;
  26
  27         while (e /= 2) {
  28                 N *= 2;
  29                 U = U * 1L * (m + 1) / 2 % m;
  30                 f (362);
  31                 for (p = t; p < t + N;)
  32                         *p++ = (*p * 1L ** p % m) * U % m;
  33
  34                 f (415027540);
  35                 for (a = 0, p = t; p < t + N;)
  36                         a += (6972593 & e ? 2 : 1) ** p, *p++ = a % 10, a /= 10;
  37         }
  38
  39         while (!*--p)
  40                 ;
  41
  42         t[0]--;
  43         {
  44                 int qs = 0;
  45                 while (p >= t)
  46                         qs += *p--;
  47                 printf ("Checksumme = %d\n", qs);
  48         }
  49         return 0;
  50 }