Основы программирования

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Разложение числа на простые множители                                  ++++ 
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 
#include <ctime>
#include <iostream>
 
 
//----------------------------------------------------------------------1----
using namespace std;
 
#define SIZE 1000
//---------------------------------------------------------------------------
 
 
//----------------------------------------------------------------------2----
//Простые множители.
int prime_factors[SIZE];                                   
 
//Их количество.
int count = 0;                                             
//---------------------------------------------------------------------------
 
 
//----------------------------------------------------------------------3----
//НОД.
int GreatestCommonDivisor(int arg1, int arg2);             
 
//Число по модулю.
int Mod(int operand, int module);                         
 
//Генератор случайных чисел.
int RndGen(int num);                                       
 
//Получение случайного множителя num.
int GenerateFactor(int num);                           
 
//Разложение на простые множители.
void Factorization(int num, int prime_factors[]);         
 
//Проверка числа на простоту.
bool IsPrime(int num);                                                                                               
 
//Вывод результатов.
void PrintResult(int num, int prime_factors[], int count);  
 
//---------------------------------------------------------------------------
 
 
//----------------------------------------------------------------------4----
int main()
{
	int num;
 
	cout << "Enter number: ";
	cin >> num;
	cout << endl;
 
	//Факторизация.
	Factorization(num, prime_factors);					   
 
	//Вывод результатов.
	PrintResult(num, prime_factors, count);	                
 
	system("PAUSE");
 
	return 0;
}
//---------------------------------------------------------------------------
 
 
//----------------------------------------------------------------------5----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Получение НОД arg1 и arg2 бинарным алгоритмом Евклида.                 ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int GreatestCommonDivisor(int arg1, int arg2)
{
	int shift;
	int difference;
 
	//НОД(0, n) = n; НОД(m, 0) = m.
	if (arg1 == 0 || arg2 == 0)
		return arg1 | arg2;
 
	/*Если m, n чётные, тогда НОД(m, n) = 2 * НОД(m / 2, n / 2).
	Пусть shift := lg K, где K наибольшая степень 2 такая, что оба числа 
	целиком делятся на 2 в степени K. */
	for (shift = 0; ((arg1 | arg2) & 1) == 0; ++shift) 
	{
		arg1 >>= 1;
		arg2 >>= 1;
	}
 
	// Если m чётное, тогда НОД(m, n) = НОД(m / 2, n).
	while ((arg1 & 1) == 0)
		arg1 >>= 1;
 
	//Далее считается, что arg1 нечетное. 
	do 
	{
		//Если n чётное, тогда НОД(m, n) = НОД(m, n / 2).		
		while ((arg2 & 1) == 0)  
			arg2 >>= 1;
 
		/*Далее считается, что arg1 и arg2 нечетные. Следовательно, 
		arg1 - arg2 четно.
		Пусть arg1 = min(arg1, arg2), arg2 = (arg1 - arg2) / 2.
		Если m, n нечётные и m < n, тогда НОД(m, n) = НОД(n - m, m).*/
		if (arg1 < arg2) 
		{
			arg2 -= arg1;
		} 
		//Если m, n нечётные и m > n, тогда НОД(m, n) = НОД(m - n, m).        
		else 
		{
			difference = arg1 - arg2;
			arg1 = arg2;
			arg2 = difference;
		}
 
		arg2 >>= 1;
	} 
	while (arg2 != 0);
 
	return arg1 << shift;
}
 
//----------------------------------------------------------------------6----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Отображение множества целых числе в кольцо [0; module]                 ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int Mod(int operand, int module)
{
	while (operand < 0) 
	{
		operand += module;
	}
 
	operand %= module;
 
	return operand;
}
//---------------------------------------------------------------------------
 
//----------------------------------------------------------------------7----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Генерация случайного числа в интервале [0; num]. Отображение в       ++++
//интервал осуществляется с помощью функции Мod(int num).                ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int RndGen(int num)
{
	srand((unsigned)time(NULL));
 
	int result;
 
	result = rand();
	result = Mod(result, num);
 
	return result;
}
//---------------------------------------------------------------------------
 
//----------------------------------------------------------------------8----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Факторизация числа. Все операции                                       ++++
//являются операциями в кольце по модулю num.                            ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Factorization(int num, int prime_factors[])
{															
	//Выход из рекурсии.
	if (IsPrime(num))     
	{   
		//Проверка числа на простоту. Если простое - то записать его.
		prime_factors[count++] = num;					   
 
		return;
	}
 
	//Текущий множитель.
	int current_multiplier;								   
 
	//В бесконечном цикле генерируем случайные множители числа.
	while (true)                                          
	{                                                   
		current_multiplier = GenerateFactor(num);          
 
		/*Получив отличный от числа множитель, выходим из цикла, чтобы 
		рекурсивно вызвать факторизацию для полученного множителя и 
		для "оставшейся" части числа.*/
		if (current_multiplier != num)					 
			break;                                      
	}													 
 
	Factorization(num / current_multiplier, prime_factors);
 
	Factorization(current_multiplier, prime_factors);
}
//---------------------------------------------------------------------------
 
//----------------------------------------------------------------------9----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Получения случайного множителя первым методом Монте-Карло.             ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int GenerateFactor(int num)
{
	//Глубина поиска случайного множителя.
	int max_steps			= 100000;					   
 
	//Текущая глубина.
	int current_step		= 0;                      
	//Постоянная c функции отображения f(n)= n ^ 2 + c.
	int polynomial_const	= 2;						   
 
	//Случайноe число в интервале [0; num].
 
	int x = RndGen(num);								  
 
	//Применим отображение f(n)= n ^ 2 + c.
	int y = Mod(x * x + polynomial_const, num);			  
 
	/*Пока НОД тривиален и глубина поиска не исчерпана применить отображение
	один раз к x и два раза к y.*/
	int divisor = GreatestCommonDivisor(abs(x - y), num);  
 
	while (current_step < max_steps && divisor == 1)	   
	{													  
		x = Mod(x * x + polynomial_const, num);			  
		y = Mod(y * y + polynomial_const, num);			   
		y = Mod(y * y + polynomial_const, num);			   
 
		divisor = GreatestCommonDivisor(abs(x - y), num);  
 
		current_step++;
	}
	//Успех == НОД нетривиален.
	return divisor;										   					
}
//---------------------------------------------------------------------------
 
//----------------------------------------------------------------------10----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Проверка числа на простоту "классическим" переборным алгоритмом.       ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool IsPrime(int num)									   
{	
	/*Брать числа, квадраты которых меньше исследуемого num, и делить
	на них num. Если num не делится нацело ни на одно из них, то оно
	простое.*/
	for (int i = 2; i * i <= num; i++)                    
		if (num % i == 0)								   
			return false;								 
 
	return true;
}
//---------------------------------------------------------------------------
 
//----------------------------------------------------------------------11----
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Вывод полученных простых множителей.                                   ++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void PrintResult(int num, int prime_factors[], int count)
{
	if (count > 1)
		cout << num << " = " << prime_factors[0] << " * " << prime_factors[1];
	else 
		cout << num << " = " << prime_factors[0];
 
	for (int j = 2; j < count; j++)
		cout << " * " << prime_factors[j];
 
	cout << endl << endl;
}
//---------------------------------------------------------------------------