阶乘（最大公约数与质数判断）

题目链接：https://ac.nowcoder.com/acm/contest/4784/B

题目描述

解析

一开始真的就是去求阶乘，发现即使n很小，n!也可以很大。然后我以为把n!控制在long long int数据内就可以了，发现这样也是不行的。那应该怎么办呢？
其实对于两个数a,b，如果a是b的倍数，那么a质因子中一定包含b的所有质因子。所以这道题就可以将p约去与1~n这n个整数所有的质因子，直到p被约为1或者成为一个质数（但是成为质数的情况也要分类讨论）。

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
	return b==0?a:gcd(b,a%b);
}
bool isPrime(int n) {
	if(n==1) return false;
	for(int i=2; i*i<=n; i++) {
		if(n%i==0) return false;
	}
	return true;
}
int main() {
	int t,p;
	cin>>t;
	while(t--) {
		cin>>p;
		int i,flag=0;
		if(isPrime(p)) printf("%d\n",p);
		else {
			for(i=2; p>1; i++) {
				int gcdval=gcd(p,i);
				p/=gcdval;	//约去最大公约数
				if(i<p&&isPrime(p)) {	//注意即使当p成为质数但是i>p还是不能break
					flag=1;
					break;
				}
			}
			printf("%d\n",flag?p:i-1);
		}

	}
	return 0;
}

这题在比赛的时候就掉了if(i<p&&isPrime(p))中的i<p这个条件…