蓝桥杯 - 找素数

深藏阁楼爱情的钟 2022-06-01 02:37 211阅读 0赞

这道题用普通的方法会超时

首先用筛素数的方法，把素数筛除来，然后在这其中，维护一个数组，记录这个数是否是素数

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    
    using namespace std;
    
    typedef long long ll;
    const int MAXN = 9999999;
    int sum = 0;
    bool is_prime[MAXN], vis[MAXN];
    
    void getprime(ll a, ll b) {
        int m = sqrt(b+0.5);
        memset(vis, true, sizeof(vis));
        for(int i = 0; i < b - a; i++)
            is_prime[i] = true;
        for(int i = 2; (ll)i * i < b; i++) {
            if(vis[i]) {
                for(int j = 2*i; (ll)j*j < b; j += i) vis[j] = false;
                for(ll j = max(2LL, (a+i-1)/i)*i; j < b; j += i) {
                    is_prime[j-a] = false;
                }
            }
        }
        return;
    }
    int main() {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        getprime(a, b+1);
        for(ll i = a; i <= b; i++) {
            if(is_prime[i-a]) sum++;
        }
        printf("%d\n", sum);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，211人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯入门即劝退（六）等差素数数列

> 九层之台，起于垒土，你我皆是垒土人✔ > 愿我的文章对你有所帮助！ > 欢迎===关注===点赞===评论，共同学习，共同进步！一、题目 2,3,5,7,

￡神魔★判官ぃ/ 2023年09月23日 14:14/ 0 赞/ 95 阅读

相关蓝桥杯题目

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

分手后的思念是犯贱/ 2023年01月12日 01:52/ 0 赞/ 293 阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 434 阅读

相关蓝桥杯—找规律

2014年第五届第1题标题：啤酒和饮料啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料

比眉伴天荒/ 2022年06月18日 05:49/ 0 赞/ 312 阅读

相关 2017蓝桥杯:等差素数列

标题：等差素数列 2,3,5,7,11,13,….是素数序列。类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。上边的数列

客官°小女子只卖身不卖艺/ 2022年06月16日 22:24/ 0 赞/ 200 阅读

相关蓝桥杯 - 找素数

这道题用普通的方法会超时首先用筛素数的方法，把素数筛除来，然后在这其中，维护一个数组，记录这个数是否是素数 include<cstdio> include

深藏阁楼爱情的钟/ 2022年06月01日 02:37/ 0 赞/ 212 阅读

相关蓝桥杯

又到了一年一度蓝桥杯，真是烦，不知道要不要参加。去年我报名了，忘了留意时间错过了。今年又大三，想学的又特别多，报名吧得花很多时间准备，可不报名吧，以后简历又不好看。参加的

傷城~/ 2022年05月07日 19:28/ 0 赞/ 367 阅读

相关蓝桥杯

又到了一年一度蓝桥杯，真是烦，不知道要不要参加。去年我报名了，忘了留意时间错过了。今年又大三，想学的又特别多，报名吧得花很多时间准备，可不报名吧，以后简历又不好看。参加的

客官°小女子只卖身不卖艺/ 2022年05月07日 05:54/ 0 赞/ 366 阅读

相关蓝桥杯圆周率

数学发展历史上，圆周率的计算曾有许多有趣甚至是传奇的故事。其中许多方法都涉及无穷级数。图1.png中所示，就是一种用连分数的形式表示的圆周率

浅浅的花香味﹌/ 2022年03月07日 10:44/ 0 赞/ 358 阅读

相关蓝桥杯试题算法训练找零钱

试题算法训练找零钱资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个

我会带着你远行/ 2021年09月24日 00:32/ 0 赞/ 369 阅读