biggest_prime.c 1.05 KB
Newer Older
Matthias Braun's avatar
Matthias Braun committed
1
#include <stdio.h>
2

Matthias Braun's avatar
Matthias Braun committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int m = 754974721;
static int N;
static int t[1 << 22];
static int a;
static int *p;
static int i;
//static int e = 1 << 22;
static int e = 1 << 10;
static int j;
static int s;
static int b;
static int c;
static int U;

void f(int d)
Christian Würdig's avatar
Christian Würdig committed
18
{
Matthias Braun's avatar
Matthias Braun committed
19
20
21
22
23
24
25
26
27
	for (s = 1 << 23; s; s /= 2, d = d * 1L * d % m) {
		if (s >= N) continue;
		for (p = t; p < t + N; p += s) {
			for (i = s, c = 1; i; i--) {
				b = *p + p[s], p[s] = (m + *p - p[s]) *
					1L * c % m, *p++ = b % m, c = c * 1L * d % m;
			}
		}
	}
28
29
30
31

	for (j = 0; i < N - 1;)
	{
		for (s = N / 2; !((j ^= s) & s); s /= 2)
Matthias Braun's avatar
Matthias Braun committed
32
		{}
33
34
35
36

		if (++i < j)
			a = t[i], t[i] = t[j], t[j] = a;
	}
Christian Würdig's avatar
Christian Würdig committed
37
38
}

39
int main ()
Christian Würdig's avatar
Christian Würdig committed
40
{
41
42
43
44
45
46
	*t = 2;
	U = N = 1;

	while (e /= 2) {
		N *= 2;
		U = U * 1L * (m + 1) / 2 % m;
Matthias Braun's avatar
Matthias Braun committed
47
		f(362);
48
		for (p = t; p < t + N;)
Matthias Braun's avatar
Matthias Braun committed
49
			*p++ = (*p * 1L * *p % m) * U % m;
50

Matthias Braun's avatar
Matthias Braun committed
51
52
53
54
55
56
		f(415027540);
		for (a = 0, p = t; p < t + N;) {
			a += (0x6A64B1 & e ? 2 : 1) * *p;
			*p++ = a % 10;
			a /= 10;
		}
57
58
59
60
61
62
	}

	while (!*--p)
		;

	t[0]--;
Christian Würdig's avatar
Christian Würdig committed
63
64
	{
		int qs = 0;
65
66
67
		while (p >= t)
			qs += *p--;
		printf ("Checksumme = %d\n", qs);
Christian Würdig's avatar
Christian Würdig committed
68
	}
69
	return 0;
Christian Würdig's avatar
Christian Würdig committed
70
}