Kody źródłowe/Rząd w grupie multiplikatywnej

C

#include <stdio.h>
#include <math.h>

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 < x; i++)
		mask0[i] = false;
	mask0[0] = true;
	int i, e;
	i = 2;
	e = (int)sqrt(x);
	while (i <= e) {
		while ((x % i) == 0) {
			x /= i;
			e = (int)sqrt(x);
			maskStep(i, n);
		}
		i++;
	}
	if (x > 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");	
	}
}