【Java】P1075 質因數分解—關于數學方法在解題中的運用—（OJ：洛谷）

題目

題目來源：洛谷OJ

題目連結：

https://www.luogu.com.cn/

題目描述

已知正整數n是兩個不同的質數的乘積，試求出兩者中較大的那個質數。

輸入格式

一個正整數n。

輸出格式

一個正整數p，即較大的那個質數。

輸入輸出樣例

輸入 #1複制

21
           

輸出 #1複制

7
           

說明/提示

n ≤ 2 × 109

NOIP 2012 普及組 第一題

思路

第一眼閱讀完題目會感覺這個題很複雜，不但要判斷質因數，還要應付龐大的資料範圍。

質因數（素因數或質因子）在數論裡是指能整除給定正整數的質數。除了1以外，兩個沒有其他共同質因子的正整數稱為互質。因為1沒有質因子，1與任何正整數（包括1本身）都是互質。正整數的因數分解可将正整數表示為一連串的質因子相乘，質因子如重複可以用指數表示。根據算術基本定理，任何正整數皆有獨一無二的質因子分解式 [1] 。隻有一個質因子的正整數為質數。（百度百科）

但是，用過質因數的定義，我們可以聯想到唯一分解定理。

算術基本定理可表述為：任何一個大于1的自然數 N,如果N不為質數，那麼N可以唯一分解成有限個質數的乘積 N = P 1 a 1 P 2 a 2 . . . . . . P n a n \N={P_1^{a_1}}{P_2^{a_2}}......{P_n^{a_n}} N=P1a1​​P2a2​​......Pnan​​，這裡P1<P2<P3…<Pn均為質數，其中指數ai是正整數。這樣的分解稱為 N 的标準分解式。（百度百科）

剩下的就簡單了，直接用輸入的數對i（i = 2, 3 ,4 ,5 ,…）求餘，倘若餘數為0，則n / i 的就是答案。

Java源代碼

package 入門3循環結構;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

/**
 *@Title P1075質因數分解.java
 *@description TODO
 *@time 2020年7月17日
 *@author Baisu
 *@version 1.0
 */
public class P1075質因數分解 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer st = new StreamTokenizer(br);
		PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		st.nextToken();
		int n = (int) st.nval;
		for(int i=2; i<n; ++i) {
			if(n%i==0) {
				pr.println(n/i);
				break;
			}
		}
		pr.flush();
	}

}