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