用int处理速度极慢，对于(n>100000)等很长时间没结果
改用__int64可以在30ms左右计算出来。
请问两者区别在哪？
代码：
#include <iostream>
using namespace std;
////accepted code
__int64 MultMod(__int64 base, __int64 pow, __int64 n)
{
	__int64 result = 1;
	while(pow)
	{
		while(!(pow&1))
		{
			base = base*base % n;
			pow >>= 1;
		}
		result = result*base % n;
		pow --;
	}
	return result;
}

bool RabbinMiller(__int64 n)
{
	__int64 t = 0;
	__int64 M = n-1;
	__int64 v;
	__int64 a,i;

	a = rand()%(n-1)+1;
	//cout <<"a="<<a<<endl;

	while(!(M&1))
	{
		t++;
		M >>= 1;
	}

	v = MultMod(a,M,n);
	
	if(v == 1)
		return true;

	i = 1;
	while(v != n-1)
	{
		if(i == t)
		{
			return false;
		}
		v = MultMod(v,2,n);
		i++;
	}
	return true;
}

bool NRabinMiller(__int64 n,int loop)
{
	if(n < 2)
		return false;
	if(n == 2)
		return true;
	else if(!(n&1))
	{
		return false;
	}
	else
	{
		int i;
		for(i = 0; i < loop; ++i)
		{
			if(!RabbinMiller(n))
				return false;
		}
	}
	return true;

}
/*
//TLE when using int;
int MultMod(int base, int pow, int n)
{
	int result = 1;
	while(pow)
	{
		while(!(pow&1))
		{
			base = base*base % n;
			pow >>= 1;
		}
		result = result*base % n;
		pow --;
	}
	return result;
}

bool RabbinMiller(int n)
{
	int t = 0;
	int M = n-1;
	int v;
	int a,i;

	a = rand()%(n-1)+1;
	//cout <<"a="<<a<<endl;

	while(!(M&1))
	{
		t++;
		M >>= 1;
	}

	v = MultMod(a,M,n);
	
	if(v == 1)
		return true;

	i = 1;
	while(v != n-1)
	{
		if(i == t)
		{
			return false;
		}
		v = MultMod(v,2,n);
		i++;
	}
	return true;
}

bool NRabinMiller(int n,int loop)
{
	if(n < 2)
		return false;
	if(n == 2)
		return true;
	else if(!(n&1))
	{
		return false;
	}
	else
	{
		int i;
		for(i = 0; i < loop; ++i)
		{
			if(!RabbinMiller(n))
				return false;
		}
	}
	return true;

}
*/

int main()
{
	int n;
	while(1)
	{
		scanf("%d",&n);
		if(n == 0)
			break;
		int left = n;
		int right = n;
		int result = 0;

		if(NRabinMiller(n,8))
			cout << 0 << endl;
		else
		{
			while(--left)
			{
				if(NRabinMiller(left,8))
					break;
			}
			while(++right)
			{
				if(NRabinMiller(right,8))
					break;
			}
			cout << right-left << endl;
		}
	}
	return 0;
}

• Re:请教int和__int64的区别 (2667) skogt 2010-10-21 20:57:46
  • Re:请教int和__int64的区别 (74) skogt 2010-10-21 21:00:34