文章

19

粉丝

0

获赞

148

访问

4.9k

头像
素数 题解:不用素数筛
P1375 北京航空航天大学机试题
发布于2025年3月14日 18:14
阅读数 183

首先数据范围不是很大,即使是纯粹的暴力遍历复杂度大概在n*sqrt(n),应该是不会超时,但数据量增加的情况下暴力判定是不是素数就会超时。普遍的解法一般是素数筛筛出1—n的素数x,然后判断x%10 == 1,尾数为1输出。但是有没有不用背并且复杂度不高的算法可以直接解决问题呢?打表!

先美美的写一个暴力到不能再暴力的代码输出10000以内所有的素数:
#include<bits/stdc++.h>
using namespace std;
bool su(int n){
    if(n <= 1)    return false;
    if(n == 2)    return true;
    bool flag = true;
    for(int i = 2; i <= sqrt(n);i++){
        if(n%i == 0){
            flag = false;
            break;
        }
    }
    if(flag)    return true;
    else    return false;
}
int main(){
    for(int i = 1;i <= 10000;i++){
        if(su(i)){
     &n...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发