TLE9个

fly__sheep @ 2024-04-07 22:12:15

#include<cstdio>
using namespace std;
int pnum(int num){
    for(int i=2;i<num/2;i++){
        if(num%i==0){
            return 0;
        }
    }
    return num;
}
int main(){
    int n,p,num;
    scanf("%d",&n);
    for(int i=2;i<n/2;i++){
        for(int j=0;j<n/2;j++){
            if(pnum(i)*pnum(j)==n){
                if(i>j){
                    num=i;
                }
                else{
                    num=j;
                }
            }
        }
    }
    printf("%d",num);
    return 0;
}

by zzgj1235 @ 2024-04-07 22:17:27

for(int i=2;i<num/2;i++)改为： for(int i=2;i*i<num;i++)

by zzgj1235 @ 2024-04-07 22:20:56

for(int j=0;j<n/2;j++)改为： for(int j=0;j*j<n;j++)

by zzgj1235 @ 2024-04-07 22:33:30

算法复杂度太高了

by fly__sheep @ 2024-04-08 12:10:39

@zzgj1235 学一下优化(

by fly__sheep @ 2024-04-08 12:45:49

#include<cstdio>
using namespace std;
int pnum(int num){
    for(int i=2;i*i<num;i++){
        if(num%i==0){
            return 0;
        }
    }
    return num;
}
int main(){
    int n,p,num;
    scanf("%d",&n);
    for(int i=2;i<n/2;i++){
        for(int j=num+1;j*j<n;j++){
            if(pnum(i)*pnum(j)==n){
                if(i>j){
                    num=i;
                }
                else{
                    num=j;
                }
            }
        }
    }
    printf("%d",num);
    return 0;
}

现在60分了@zzgj1235

by WhiteNight__ @ 2024-05-02 23:35:05

@fly_sheep

如果一个数可以被分解成两个素数的乘积，那么这一个数只能被分解成两个素数的乘积

因此不用两层循环枚举每一个可行素数，只用一层枚举可行素数，然后另一个算出来，取最大值就可以了

by SuperJAR @ 2024-05-03 20:41:29

根据上面dalao的思路，我简单补写一下代码

#include<iostream>
#include<fstream>
#include <iomanip>
#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
    int n,s=0,f=0,flag=1;
    cin>>n;
    for(int j=2;j*j<=n;j++){
        int m=1;
        for(int i=2;i*i<=j;i++){
            if(j%i==0){
                m=0;break;
            }   
        }
        if(!m) continue;
        for(int t=j;t<=n/j;t++){
            int k=1;
            for(int g=2;g*g<=t;g++){
                if(t%g==0){
                    k=0;break;
                }   
            }
            if(!k) continue;
            if((j*t)==n){
                if(j>t) cout<<j;
                else cout<<t;
                flag=0;break;
            }
        }
        if(flag==0) break;
        }
    return 0;
}

by Zhengyunshu @ 2024-05-25 22:40:50

@zzgj1235 你被棕了

by wangshuyan @ 2024-06-21 19:29:38

#include <iostream>
using namespace std;

int main () {
    int n;
    cin >> n;

    for (int i = 2;; i++) {
        if (n % i == 0) {
            cout << n / i;
            break;
        }
    }

    return 0;
}

by xujinchen087 @ 2024-07-25 11:44:28

你那算什么，我是个TLE呢。