資訊學奧賽一本通 1098：質因數分解 | 1957：【12NOIP普及組】質因數分解 | OpenJudge NOI 1.5 43

【題目連結】

ybt 1098：質因數分解

ybt 1957：【12NOIP普及組】質因數分解

OpenJudge NOI 1.5 43:質因數分解

【題目考點】

1. 質因數

【解題思路】

題目中給的數字n是兩個質數的乘積，n的範圍最大能達到 2 9 2^9 29

除非二者相等，其它情況下，都是一個較小的質數乘以一個較大的質數。

顯然，搜尋較小的質因數更容易。

因為數字n是兩個質數的乘積，因而數字n隻能整除這兩個質數。

循環變量i從2開始不斷增大，判斷n是否能被i整除（i是否是n的因數），如果是，那麼i就是n的兩個質因數中較小的質因數。那麼較大的質因數就是n / i。

【題解代碼】

解法1：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i = 2; i <= n; ++i)
    {
        if(n % i == 0)//第一個找到的n的因數i，一定是n的兩個質因數中較小的質因數 
        {
            cout<<n / i<<endl;//n / i就是n的兩個質因數中較大的質因數 
            return 0;
        }
    }
    return 0;
}