深圳网站建设制作培训/seo网站排名优化公司

//
问题 A: 质因数分解
时间限制: 1.000 Sec  内存限制: 128 MB题目描述
已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。
输入
输入只有一行，包含一个正整数n。6 ≤ n ≤ 2*109
输出
输出只有一行，包含一个正整数p，即较大的那个质数。
样例输入 Copy
21
样例输出 Copy
7

repeat(2)_欧氏筛

// A
#include<bits/stdc++.h>
using namespace std;// 6 ≤ n ≤ 2*109
const int N=2e9+10;     
const int small=2e5+6;  // prime[i]*prime[i]<=n
bool judge[small];       
int prime[small];
// Error: value of 00000002540be678 too large for field of 4 bytes at 0000000000000210void sieve( int n )
{int cnt=0,i,j;memset( judge,0,sizeof( judge ) );memset( prime,0,sizeof( prime ) );for( i=2;i<=n;i++ ){if( judge[i]==false ) prime[cnt++]=i;for( j=0; j<cnt && prime[j]<=n/i ;i++ ){judge[ i*prime[j] ]=true;if( i%prime[j]==0 ) break;}}
}int main()
{int n,i; sieve( small-5 );while( ~scanf("%d",&n) ){for( i=0; prime[i]<=n/prime[i] ;i++ ){if( n%prime[i]==0 ) break;}printf("%d\n",n/prime[i]);}return 0;
}