__int64 PollardRho (const __int64 &c,const __int64 &test)
{
	__int64 y,x,gcd;
	int i,k;

	y = x = rand () % test;
	i = 1;
	k = 2;
	do
	{
		i++;
		gcd = Gcd (2 * test + y - x,test);
		if (gcd > 1 && gcd < test)
		{
			return gcd;
		}
		if (i == k)
		{
			y = x;
			k *= 2;
		}
		x = (x * x + test - c) % test;
	}while (x != y);
	
	return test;
}
		
//----------------------------------------------

//----------------------------------------------
void Rho (const __int64 &test)
{
	__int64 n;

	if (MillerRabin (test,2))
	{
		if (test < min)
		{
			min = test;
		}
	}
	else
	{		
		n = PollardRho (rand() % (test - 1) + 1,test);
	                if (n < test)
		{
	     	       Rho (n);
	    	       Rho (test / n);
		}
	}
}

• 随机算法就是这样的啦，有一点点的问题就挂了 (880) frkstyc 2005-07-09 22:17:23
  • 能发段通过的来看看吗？就发Pollard部分的，谢谢：） (0) queyue2004 2005-07-09 22:21:40