1313 質(zhì)因數(shù)分解

2012年NOIP全國(guó)聯(lián)賽普及組

時(shí)間限制: 1 s 空間限制: 128000 KB 題目等級(jí) : 青銅 Bronze 題目描述 Description

已知正整數(shù) n是兩個(gè)不同的質(zhì)數(shù)的乘積，試求出較大的那個(gè)質(zhì)數(shù) 。

輸入描述 Input Description

輸入只有一行，包含一個(gè)正整數(shù) n。

輸出描述 Output Description

輸出只有一行，包含一個(gè)正整數(shù)p，即較大的那個(gè)質(zhì)數(shù)。

樣例輸入 Sample Input

21

樣例輸出 Sample Output

7

數(shù)據(jù)范圍及提示 Data Size & Hint

【數(shù)據(jù)范圍】

?對(duì)于60%的數(shù)據(jù)，6≤n≤1000。

?對(duì)于100%的數(shù)據(jù)，6≤n≤2*10⁹。

?

看到10的9次方我就懵了，vis【】素篩數(shù)組都開(kāi)不了，沒(méi)想到幾行代碼就搞定了

1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int is_prime(int a) 5 { 6 for (int i=2; i<=sqrt(a); i++) 7 if (a%i==0) 8 return 0; 9 return 1; 10 } 11 int main() 12 { 13 int n,i,j,q; 14 cin>>n; 15 for (i=1; i<=sqrt(n); i++) 16 { 17 if (n%i==0&&is_prime(i)&&is_prime(n/i)) 18 { 19 cout << n/i << endl; 20 break; 21 } 22 } 23 return 0; 24 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lyqlyq/p/6841543.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的1313 质因数分解 2012年NOIP全国联赛普及组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。