相邻的两个素数p和p + n之间的n - 1个连续的合数所组成的序列，称为长度为n的素数槽。

例如，24, 25, 26, 27, 28 是处于素数23和素数29之间的一个长度为6的素数槽。

写一个程序来计算：包含整数k的素数槽的长度。如果k本身就是素数，那么认为包含k的素数槽的长度为0。

Input
多测试用例。第一行是一个数字n，表示测试用例的个数。

接下来有n行，每行是一个正整数k， k大于1并且小于或等于第十万个素数（也就是1299709）。

Output
对于输入的每一个k，都对应输出一个非负整数，表示包含k的素数槽的长度，每个非负整数占一行。


代码如下：
#include<stdio.h>
#include<math.h>
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int m,y,i,t=0;
        scanf("%d",&m);

        for(i=m;;i++)
        {
            y=0;
            for(int j=2;j<=sqrt(i);j++)
                if(i%j==0)y=1;
            if(y!=1&&i==m)
                {printf("0\n");break;}
            else if(y!=1&&i!=m)
                {t=1;break;}
        }

        if(t==1)
        {
            for(int k=m-1;;k--)
            {
                y=0;
                for(int j=2;j<sqrt(i);j++)
                    if(k%j==0)y=1;
                if(y!=1)
                    {printf("%d\n",i-k);break;}
            }
        }


    }
    return 0;
}

没人吗

有哪位大佬来指点一下吗一直超时，有没有什么更快的算法

。。。

我感觉这两个地方可以改一下：
(1)判断出一个数不是素数时，没有及时跳出判断，而是继续判断，直到sqrt(m)，可以设法使其及时跳出；
(2)寻找相邻的素数时用到了嵌套，造成了大量的时间浪费，并且是无谓的，可以将其改为两个独立的循环；


这是我写的代码，没有用到更快的算法，只是按照上面我说的那两个问题改进了一下，你试试，如果还是慢那我就不会了...

#include<stdio.h>
#include<math.h>

int isprime(int);

int main(void)
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int min_prime, max_prime, prime, m;
        scanf("%d", &m);
        if ( isprime(m) )
            printf("0\n");
        else
        {
            for (prime = m - 1; !isprime(prime); prime--);
            min_prime = prime;
            for (prime = m + 1; !isprime(prime); prime++);
            max_prime = prime;
            printf("%d\n", max_prime - min_prime);
        }
    }
    return 0;
}

int isprime(int n)
{
    if (n > 1)
    {
        int i;
        for (i = 2; n % i && i <= sqrt(n); i++);
        if ( i > sqrt(n) )
            return 1;
    }
    return 0;
}

[此贴子已经被作者于2018-12-17 18:41编辑过]

#include<stdio.h>
#include<math.h>
int main()
{
    int sushu(int k);
    int n;
    int k;
    int i,j;
    int sc=0;
    scanf("%d",&n);
    while(n)
    {
    scanf("%d",&k);
    for(i=k;sushu(i);i++);
    for(j=k;sushu(j);j--);
    if(j==k)
        sc=0;
    else
        sc=i-j;
    printf("%d\12",sc);
    }
    return 0;
}
int sushu(int k)
{
    int i;
    for(i=2;i<=(int)sqrt(k);i++)
    {
        if(k%i==0)
            break;
    }
    if(i>sqrt(k))
        return 0;
    else
        return 1;
}

#include<stdio.h>
#include<math.h>
int main()
{
    int sushu(int k);
    int n;
    int k;
    int i,j;
    int sc=0;
    scanf("%d",&n);
    while(n)
    {
    scanf("%d",&k);
    for(i=k;sushu(i);i++);
    for(j=k;sushu(j);j--);
    if(j==k)
        sc=0;
    else
        sc=i-j;
    printf("%d\12",sc);
    }
    return 0;
}
int sushu(int k)
{
    int i;
    for(i=2;i<=(int)sqrt(k);i++)
    {
        if(k%i==0)
            break;
    }
    if(i>sqrt(k))
        return 0;
    else
        return 1;
}