題目描述

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

思路

從n-1開始嘗試能不能被n整除，能被整除的就是較大的那個(gè)質(zhì)數(shù)。

#include<iostream> using namespace std; int main() {long long int n;cin>>n;for(long long int x=n-1;x>1;x--){if(n%x==0){cout<<x<<endl;break;}}return 0; }

但是這樣會(huì)超時(shí)。

網(wǎng)上的解法是從2開始遍歷到sqrt(n)
這是一種剪枝辦法。

#include<iostream> using namespace std; int main() {long long int n;cin>>n;for(long long int x=2;x<sqrt(n);x++){if(n%x==0){cout<<n-x<<endl;break;}}return 0; }

個(gè)人感覺 x的范圍n 就可以了，因?yàn)榉凑龝?huì)提前 break

總結(jié)

以上是生活随笔為你收集整理的已知两个质数乘积n，求较大的那个质数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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