质因数分解3种方法

描述

已知正整数n是两个不同的质数的乘积试求出较大的那个质数。

输入描述

输入只有一行包含一个正整数n。

输出描述

输出只有一行包含一个正整数p, 即较大的那个质数。

样例输入 21

样例输出 7

//方法一： 倒着找最大的质因数，正确率60%，其它的超时
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int x){
    int flag=100;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            flag=-1;
            return false;
        }
    }
    if(flag==100){
        return true;
    }
    
    
}

int main(){
    
    int n;
    cin>>n;
    
    for(int i=n-1;i>1;i--){
        if(n%i==0){//是它的因数，再判断因数是不是素数
            if(isPrime(i)==true){
            cout<<i;
            break;
        }
        }
        
    }
    return 0;
}

方法二：用埃式筛选法，找质因数，正确率90%，其它超时
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int n;
    cin>>n;
    
    //埃式筛选法 
    int i=2,maxi=-1;
    while(n!=1){
        while(n%i==0){
            maxi=i;
            n/=i;
        }
        i++;
    }
    cout<<maxi;
    return 0;
}

方法三：找最小的质因数，然后用它除以最小的质因数，则得到最大的质因数，正确率100%。 还可以优化成用埃式筛选法找最小的质因数，然后再反着求最大的质因数。
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int x){
    int flag=100;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            flag=-1;
            return false;
        }
    }
    if(flag==100){
        return true;
    }
}


int main(){
    
    int n;
    cin>>n;
    
    //找最小的质数，另一个因数也会是质数
    for(int i=2;i<n;i++){
        if(n%i==0){//是因数，再判断这个因数是不是质数 
            if(isPrime(i)==true){
                cout<<n/i;
                break;
            }
            
        }
    }
    
    
    return 0;
}