TYVJ P2067(質因數分解）

P2067 - [NOIP2012P1]質因數分解
From luchangzhou    Normal (OI)
總時限：10s    內存限制：128MB    代碼長度限制：64KB
背景 Background

NOIP2012
描述 Description

已知正整數n 是兩個不同的質數的乘積，試求出較大的那個質數。
輸入格式 InputFormat

 輸入只有一行，包含一個正整數n 。
輸出格式 OutputFormat

 輸出只有一行，包含一個正整數p ，即較大的那個質數。
樣例輸入 SampleInput [復制數據]

21
樣例輸出 SampleOutput [復制數據]

7
數據范圍和注釋 Hint

【數據范圍】
對於 60% 的數據 6 ≤ n ≤ 1000
對於 100%的數據 6 ≤ n ≤ 2*10^9
來源 Source

NOIP2012

O（√n）
注意要枚舉1-√n而不是√n-n，數量級差很多。

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<cstdlib> 
#include<cctype> 
#include<iostream> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (100000+10) 
#define MAXAi (1000000000+10) 
int n; 
int main() 
{ 
    cin>>n; 
    for (int i=2;i<=n;i++) 
        if (!(n%i)) 
        { 
            cout<<n/i<<endl;return 0; 
        }  
     
         
}