int Ferma(int n)//метод нахождения делителя числа
	{
		if (n == 1)
			return 1;
		if (RabMill(n))//проверяем на простоту
		{
			label3+= n+";";//записали простое число в список
			return n;//n простое
		};
		if (n % 2 == 0)//проверяем на четность
		{
			label3 += "2;";//если четное то добовляем в список
			Ferma(n/2);//проверяем второе число методом ферма
			return 1;//найден делитель
		};
		bool bb = true;
		for(int i = 0; i < 10 && bb; i++)
		{
			if (n % pk[i] == 0)
			{
				label3 += pk[i]+";";//если четное то добовляем в список
				Ferma(n/pk[i]);//проверяем второе число методом ферма
				bb = false;
			}
		}
		if (!bb)
			return 1;
		ull x_min = round(sqrt(n + 0.0) + 0.5);
		ull x_max = round(n/2 + 1 - 0.5);
		bb = true;
		while (x_min <= x_max && bb)
		{
			ull t = round(pow(x_min + 0.0,2))-n;
			ull y = round(sqrt(t + 0.0));
			if (y * y == t)
			{
				Ferma(x_min+y);
				Ferma(x_min-y);
				bb = false;
			}
			x_min += 1;
		}
		return 1;
	}

void main()
{
	//небольшие простые числа
		pk[0] = 3;
		pk[1] = 5;
		pk[2] = 7;
		pk[3] = 11;
		pk[4] = 13;
		pk[5] = 17;
		pk[6] = 19;
		pk[7] = 23;
		pk[8] = 29;
		pk[9] = 31;
		cout<<"vvedite n:"<<endl;
		int n;
		cin>>n;
		cout<<"vvedite k:"<<endl;
		int k;//заносим второе значение
		cin>>k;
		num2=k;
		int t,S;
		bool b = (n % 2 != 0);
		if (b)
			GetTS(n-1,&t,&S);
		int i = 0;
		clock_t T = clock();
		for (i; i < k && b; i++)
		{
			int a = rand() % n;//случайное значение в диапазоне n
			if (a < 2)
				a = 2;// делаем нижнюю границу случайного числа равной 2
			b = (gcd(a,n) == 1);// проверяем наибольший общий делитель a и n
			if (b)
			{
				ull z = round(pow(a+0.0,t)) % n;//Вычисляем z = a^t mod n
				if (z != 1)//Если z ≡ &plusmn;1 (mod n), то переходим к шагу 1
				{
					for (int ii = 0; ii < S && b; ii++)//Вычисляем a^t mod n, a^(2t) mod n, … , a^(2^(S-1)t) mod n
					{									//до тех пор, пока не появится –1
						if (round(pow(a + 0.0, (pow(2.0, ii)) * t)) % n == 1)
							b = false;//поевилась 1,иначе b=true
					}
				}
			}
		}
		T = clock()-T;
		if (!b)
			cout<<"n- sostavnoe;  "<<endl;
		else
			cout<<"n- predpologitelno prostoe;  "<<endl;
		cout<<"kol-vo operaciy: "<<i<<";  vremya osnovnogo cikla : "<<(T*1000/CLK_TCK)<<"ms.;  "<<endl;
		if (!b)
		{
			label3 = "";
			T = clock();
			int y = Ferma(n);
			T = clock()-T;
			cout<<"delitel chisla n: ";
			for (int i9 = 0; label3[i9]; i9++) cout.put(label3[i9]) ; 
			cout<<"; vremia osnovnogo cikla : "<<(T*1000/CLK_TCK)<<"ms.;  "<<endl;
		}
		system("pause");

};