1313 质因数分解 2012年NOIP全国联赛普及组

1313 质因数分解

2012年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 青铜 Bronze

题目描述 Description

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

输入描述 Input Description

输入只有一行，包含一个正整数 n。

输出描述 Output Description

输出只有一行，包含一个正整数p，即较大的那个质数。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【数据范围】

对于60%的数据，6≤n≤1000。

对于100%的数据，6≤n≤2*10⁹。

看到10的9次方我就懵了，vis【】素筛数组都开不了，没想到几行代码就搞定了

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int is_prime(int a) 
 5 {      
 6     for (int i=2; i<=sqrt(a); i++)
 7         if (a%i==0)
 8             return 0;
 9     return 1;
10 }
11 int main() 
12 {
13     int n,i,j,q;
14     cin>>n;
15     for (i=1; i<=sqrt(n); i++) 
16     {
17         if (n%i==0&&is_prime(i)&&is_prime(n/i)) 
18         {
19             cout << n/i << endl;                                
20             break;
21         }
22     }
23     return 0;
24 }