文章

246

粉丝

0

获赞

1179

访问

74.6k

头像
连续合数段 题解:
P1493 北京航空航天大学机试题
发布于2026年3月13日 15:05
阅读数 182

#include<iostream>
#include<vector>
using namespace std;

const int N=1e5+10;

/*思路:记录素数的位置,中间隔的就是合数*/

int a,b;
int c[N];
vector<int> lens;

bool check(int n)
{
    if(n<=1)
    return false;
    if(n==2)
    return true;
    for(int i=2;i*i<=n;i++)
    if(n%i==0)
    return false;
    return true;
}

int main()
{
    int res=-1,pos=-1;
    cin>>a>>b;
    if(!check(a))
    lens.push_back(a-1);
    for(int i=a;i<=b;i++)
    {
        if(check(i))
        lens.push_back(i);
    }
    if(!check(b))
    lens.push_back(b+1);
    for(int i=0;i+1<lens.size();i++)
    {
        int nums=lens[i+1]-lens[i]-1;
        if(nums>res)
        {
            res=nums;
            pos=lens[i]+1;
        }
    }
    for(int i=pos;i<pos+res;i++)
    cout<<i<<" ";
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发