38:質因數分解
總時間限制:??? 1000ms?? 內存限制:??? 65536kB
描述
??? 已知正整數 n 是兩個不同的質數的乘積，
?? ?試求出較大的那個質數。
輸入
??? 輸入只有一行，包含一個正整數 n。
??? 對于60%的數據，6 ≤ n ≤ 1000。
??? 對于100%的數據，6 ≤ n ≤ 2*10^9。
輸出
??? 輸出只有一行，包含一個正整數 p，即較大的那個質數。
樣例輸入
??? 21
樣例輸出
??? 7
來源??? NOIP2012復賽 普及組 第一題

?

分析：

這個題目要注意“正整數 n 是兩個不同的質數的乘積”這個條件。假定n是由p和q兩個質數相乘得到的，那么n只有1，n，p，q四個因數。所以，對n枚舉除了1和n之外的因數，只要發現即可解決問題。

1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 long n,i,t; 5 scanf("%ld",&n); 6 t=n/2; 7 for(i=2;i<=t;i++) 8 { 9 if(n%i==0) 10 { 11 printf("%ld\n",n/i); 12 break; 13 } 14 } 15 return 0; 16 }

?

總結

以上是生活随笔為你收集整理的38:质因数分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。