题目

原神是一款由米哈游开发的开放世界游戏，后面忘了（

我们的主角小f来到了美丽的提瓦特大陆，跟随小派蒙的引导来到了自由之城——蒙德城，被风神巴巴托斯巴托巴斯大人忽悠去挑战风魔龙。战斗过程中，小f发现风魔龙身体十分特殊。他的身上有着 n 段数字，只有攻击一段数字中的素数才能对其造成伤害。小f需要快速解决战斗，但是他太笨了，需要你的帮助。请你编写一个程序，找出这 n 段数字中的素数，帮他解决战斗。

愿风神忽悠你

输入：第一行输入一个整数 n，代表风魔龙身上的数字段数；第二行到第 n+1 行每行两个整数 l, r，表示风魔龙身上的数字段为 [l, r]。
输出：输出共 n 行，每一行间的素数用空格隔开，输出完一段数字中的素数后需要换行。如果闭区间内不存在素数，只用输出一段换行。
数据范围：n ≤ 50，l, r ≤ 10000。

样例：

输入

3
1 100
101 200
201 300

输出

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293

思路

写一个 isPrime 函数判断单个数是否为素数：x < 2 返回 false，x == 2 返回 true，偶数返回 false， 否则从 3 到 √x 步长 2 试除。主函数对每段 [l, r] 遍历调用函数， 素数依次输出，每段结束换行。

C++ · p71.cpp 
#include<bits/stdc++.h>
using namespace std;

bool isPrime(int x){
    bool prime_flag=true;
    for(int c=3;c*c<=x;c+=2){
        if(x%c==0){
            prime_flag=false;
        }
    }
    if(x<2){
        return false;
    }else if(x==2){
        return true;
    }else if(x%2==0){
        return false;
    }else if(!prime_flag){
        return false;
    }else{
        return true;
    }
}

int main(){
    int n;
    cin>>n;
    bool first=true;
    for(int c=0;c<n;c++){
        int l,r;
        cin>>l>>r;
        for(int c1=l;c1<=r;c1++){
            if(isPrime(c1)){
                if(!first) cout<<" ";
                cout<<c1;
                first=false;
            }
        }
        first=true;
        cout<<""<<endl;
    }
    return 0;
}

复杂度分析

  • 时间复杂度：O(n·(r−l)·√r)，每段遍历区间内每个数，每个数试除到 √x。
  • 空间复杂度：O(1)。
今日感受

for 循环终止条件要写 c*c <= x，写成 < 会漏掉 c 恰好等于 √x 的情况（比如 x=9 漏掉 c=3）。 主函数里 first 标志、换行、重置的位置也要仔细——每段开始前重置，每段结束后换行，空格只在打出素数之前才打。

← 返回菜鸟的coding