给出L,R求[L,R]内相距最近的素数对,和最远的素数对。如果有同样的,输出靠前的一对

简介: 给出L,R求[L,R]内相距最近的素数对,和最远的素数对。如果有同样的,输出靠前的一对
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
bool vis[maxn],note[maxn];
int a[maxn];
ll l,r;
void get_prime()
{
    memset(vis,0,sizeof(vis));
    memset(note,0,sizeof(note));
    for(ll i=2;i*i<=r;i++)
    {
        if(vis[i]==0)
        {
            for(ll j = i+i;j*j<=r;j+=i)
                vis[j]=1;
            for(ll j=max(2ll,(l+i-1)/i)*i;j<=r;j+=i)
                note[j-l]=1;//此处防溢出
        }
    }
}
int main()
{
    while(cin>>l>>r)
    {
        if(l==1)
            l++;
        get_prime();
        int ok = 0 ;
        int tot=0;
        for(int i =0;i<=r-l;i++)
        {
            if(note[i]==0)
            {
                ok=1;
                a[tot++]=i+l;
            }
        }
        if(!ok||tot==1)
        {
            cout<<"There are no adjacent primes."<<endl;
        }
        else
        {
            int maxx=-1,minn=0x3f3f3f3f;
            int l1,r1,l2,r2;
            for(int i=tot-1;i>0;i--)
            {
                ll md=a[i]-a[i-1];
                if(md>=maxx)
                {
                    maxx=md;
                    r1=i;
                }
                if(md<=minn)
                {
                    minn=md;
                    r2=i;
                }
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",a[r2-1],a[r2],a[r1-1],a[r1]);
        }
    }
}
目录
相关文章
|
5月前
|
Python
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
|
2月前
|
C语言
【C语言】输入一个数n,输出从n到n+100的范围内所有的素数,并统计素数的个数
【C语言】输入一个数n,输出从n到n+100的范围内所有的素数,并统计素数的个数
24 0
|
2月前
打印100~200之间的素数
打印100~200之间的素数
|
7月前
|
C语言
【C语言】输入一个正整数,判断其是否为素数
【C语言】输入一个正整数,判断其是否为素数
177 0
【C语言】输入一个正整数,判断其是否为素数
|
9月前
判断10-105之间有多少个素数,并输出所有素数。【素数又称为质数,定义为在大于1的 自然数中,除了1和它本身以外不再有其他因数的数
判断10-105之间有多少个素数,并输出所有素数。【素数又称为质数,定义为在大于1的 自然数中,除了1和它本身以外不再有其他因数的数
48 0
|
9月前
编写判断一个正整数是否为素数的函数
编写判断一个正整数是否为素数的函数
输出100以内的素数(质数)
输出100以内的素数(质数)
107 0
|
机器学习/深度学习 算法
算法:从键盘循环输入一个整数,判断是否是素数\质数
算法:从键盘循环输入一个整数,判断是否是素数\质数
C#求任意范围素数
C#求任意范围素数
115 0
C#求任意范围素数
输出100-200之间的素数
输出100-200之间的素数
124 0
输出100-200之间的素数

热门文章

最新文章