C #include #include

const int MAX_SIZE = 1000; bool mask0[MAX_SIZE], mask1[MAX_SIZE];

void maskStep(int step, int n) { int i = step; while (i < n) { mask0[i] = true; i += step;

void factor(const int n) { int x = n; for (int i = 0; i 1) maskStep(x, n); }

void powers(int n, int a) { printf("%d): ",a); int rest = 1; int prev = 0; int k = 0; for (int i = 0; i < n; i++) mask1[i] = false; while (true) { rest = (rest*a) % n; if (mask1[rest]) break; printf("%d ", rest); mask1[rest] = true; k++; prev = rest;

if (prev == 1) printf("// rząd %d\n", k); else printf("// %d nie względnie pierwsze z %d\n", a, n); }

void orders(int n) { factor(n); printf("%d:\n", n); int ncoprimes = 0; for (int i = 0; i < n; i++) if (mask0[i]) ncoprimes++; for (int a = 0; a < n; a++) { powers(n, a); int coprimes = 0; for (int i = 0; i < n; i++) if (!mask0[i] & mask1[i]) coprimes++; if (coprimes+ncoprimes == n) printf("powyzszy to pierwiastek pierwotny\n");