为什么会RE啊？

Qph123456 @ 2024-07-16 22:44:49

#include<bits/stdc++.h>
using namespace std;
int n,maxx=0;
bool bol[1000000011];
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(!bol[i])
        {
            for(int j=i+1;j*i<=n;j++)
            {
                bol[i*j]=1;
            }
        }
    }
    for(int i=7;i<=n;i++)
    {
        if(!bol[i]&&n%i==0&&maxx<i)
        {
            maxx=i;
        }
    }
    cout<<maxx;
    return 0;
}

by _FJ_ @ 2024-07-16 22:51:39

数组太小？

by _8008008 @ 2024-07-16 22:54:22

@cleveraaa @Qph123456 数组太大

by _8008008 @ 2024-07-16 22:56:40

@Qph123456 有更简便的解法，你的解法正确，但是空间不支持

by zcy_jake @ 2024-07-16 23:01:04

@Qph123456

感觉是时间复杂度过于离谱。
你的程序应该是O(n^2)。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n;
bool check(int x){
    if(x == 2) return 1;
    for(int i = 2 ; i < sqrt(x) ; i ++)
        if(x % i == 0) return 0;
    return 1;
}
signed main(){
    cin >> n;
    for(int i = 2 ; i < n ; i ++) {
        if(n % i == 0 && check(i)) {
            cout << n / i << endl;
            break;
        }
    }
    return 0;
}

标程给你了，应该是O(n)左右。
求关(QWQ)

by Qph123456 @ 2024-07-17 00:29:06

@zcy_jake 非常感谢

by liuhaoyan0323 @ 2024-07-17 01:26:02

@Qph123456 哥哥，仔细读题，这不是一道水题吗，m一定为两质数成绩，那么倒着从m-1便利，如果当前i为质数，直接输出就行了，你是真六，注意审题！

by liuhaoyan0323 @ 2024-07-17 01:29:58

@Qph123456 Re是因为n≤10^9，而按你i,j乘积，10^{18}，不炸才怪

by zcy_jake @ 2024-07-17 09:17:45

@liuhaoyan0323

他应该只是没想到思路

by huangzicheng114514 @ 2024-09-08 14:40:35

太简单了，甚至不用判断质数─=≡Σ(((つ•̀ω•́)つ ！！！ https://www.luogu.com.cn/discuss/918538 可以看看我和其他人的做法。连判断质数都不用！！！ 简单的枚举！！！ 秒了！！！ 核心代码：

while(1){
    if(a%b==0){cout<<a/b;
    break;}
        else b++;//TODO

}