[NOIP2012 普及组] 质因数分解 - 洛谷

[NOIP2012 普及组] 质因数分解

题目描述

已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 n。

输出格式

输出一个正整数p，即较大的那个质数。

样例 #1

样例输入
21
样例输出
7
提示

1 <= n<=2* 10^9

NOIP 2012 普及组 第一题

代码区：

#include<stdio.h>
#include<math.h>
int factor(long long a);
int main()
{
	long long n,i;
	scanf("%lld",&n);
	for(i=2;i<=n;i++){
		if(factor(i)==1&&factor(n/i)==1&&(n%i==0)){	
			printf("%lld",n/i);
			break;
		}
			
	}
    return 0;
	
}	
int factor(long long a)
{
	int flag=1,i;
	if(a==1)
	flag= 0;
	if(a==2)
	flag=1;
	for(i=2;i<=sqrt(a);i++){
		if(a%i==0){
			flag=0;
			break;
		}
		flag= 1;
	}
	return flag;
}