poj1811.c

pku 1811 solution pku 1811 solution

	15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, \
	15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, \
	15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, \
	15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, \
	15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, \
	15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, \
	15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, \
	16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, \
	16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, \
	16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, \
	16349, 16361, 16363, 16369, 16381
};

int miller_rabin(unsigned __int64 m)
{
	if(m > 2 && powermod(2, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 3 && powermod(3, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 5 && powermod(5, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 7 && powermod(7, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 11 && powermod(11, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 13 && powermod(13, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 17 && powermod(17, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 19 && powermod(19, m - 1, m) != 1)
	{
		return 0;
	}
	if(m > 23 && powermod(23, m - 1, m) != 1)
	{
		return 0;
	}
	return 1;
}

unsigned __int64 gcd(unsigned __int64 a, unsigned __int64 b)
{
	int z = 0;
	while(b != 0 && a != 0)
	{
		while((a & 1) == 0 && (b & 1) == 0)
		{
			z++;
			a >>= 1;
			b >>= 1;
		}
		while((a & 1) == 0)
		{
			a >>= 1;
		}
		while((b & 1) == 0)
		{
			b >>= 1;
		}
		if(a > b)
		{
			a -= b;
		}
		else
		{
			b -= a;
		}
	}
	if(b == 0)
	{
		return a << z;
	}
	return b << z;
}

unsigned int brute_force64(unsigned __int64 m)
{
	int i;
	for(i = 0; prime[i] * prime[i] <= m && i < 1900; i++)
	{
		if(m % prime[i] == 0)
		{
			return prime[i];
		}
	}
	return -1;
}

unsigned int brute_force(unsigned int m)
{
	int i;
	for(i = 0; prime[i] * prime[i] <= m && i < 1900; i++)
	{
		if(m % prime[i] == 0)
		{
			return prime[i];
		}
	}
	return -1;
}

unsigned int pollard_rho(unsigned __int64 m)
{
	unsigned __int64 d = 1;
	unsigned __int64 fd, fm, y;
	int i, k;
	unsigned __int64 x = 43;
	y = x;
	k = 2;
	i = 1;
	for(;;)
	{
		__int64 diff;
		++i;
		x = (mulmod(x, x, m) + m - 1) % m;
		if(x > y)
		{
			diff = x - y;
		}
		else
		{
			diff = y - x;
		}
		d = gcd(diff, m);
		if(d != 1 && d != m)
		{
			break;
		}
		else
		{
			if(i == k)
			{
				y = x;
				k <<= 1;
			}
		}
	}
	m /= d;
	if(miller_rabin(d) == 0)
	{
		if(d <= 4294967295)
		{
			fd = brute_force((unsigned int)d);
		}
		else
		{
			fd = brute_force64(d);
		}
		if(fd == 4294967295)
		{
			fd = pollard_rho(d);
		}
	}
	else
	{
		fd = d;
	}
	if(miller_rabin(m) == 0)
	{
		if(m <= 4294967295)
		{
			fm = brute_force((unsigned int)m);
		}
		else
		{
			fm = brute_force64(m);
		}
		if(fm == 4294967295)
		{
			fm = pollard_rho(m);
		}
	}
	else
	{
		fm = m;
	}
	return (unsigned int)(fd < fm ? fd : fm);
}


unsigned int factor(unsigned __int64 m)
{
	unsigned int f;
	if(m > 4294967296)
	{
		f = brute_force64(m);
	}
	else
	{
		f = brute_force((unsigned int)m);
	}
	if(f != -1)
	{
		return f;
	}
	if(m <= 4294967295)
	{
		return (unsigned int)m;
	}
	return pollard_rho(m);
}

int main(void)
{
	unsigned __int64 m;
	int n;
	_controlfp(_PC_64, _MCW_PC);
	scanf("%d", &n);
	while(n > 0)
	{
		scanf("%I64u", &m);
		if(miller_rabin(m) != 0)
		{
			puts("Prime");
		}
		else
		{
			printf("%u\n", factor(m));
		}
		n--;
	}
	return 0;
}