1500 Prime Gap

TAG 数论 素数

预处理把所有素数求出，用二分法求该数的下标。

0.05s 1916KB

不过时间、空间复杂度好像不如沿n向两端枚举。。(‖▔ ω▔)，跟数据规模有关吧。。

这里用了改进的线性筛法，普通的筛法因为一个数有多个约数，会被重复刷掉很多次。

void makeprime()
{
	total=-1;
	memset(isprime, true, sizeof(isprime) );
	for (int i=2; i<=1299709; ++i)
	{
		if ( isprime[i] )
		{
			num[ ++total ]=i;
		}
		for (int j=0; j<=total&& i*num[j]<=1299709; ++j)
		{
			isprime[i*num[j]]=false;
			if ( i%num[j]==0 )
			{
				break;
			}
		}
	}
}

程序：

/* source code of submission 428628, Zhongshan University Online Judge System */
#include <stdio.h>
#include <memory.h>
const int N=100000;
int  num[N];
bool isprime[1299709+2];
int  total;
int  s,t,n;
int bin_search(int s,int t,int x)
{
    int mid;
    int ret;
    while ( s<=t )
    {
        mid=(s+t)/2;
        if ( num[mid]==x )
        {
            return mid;
        }
        else if ( num[mid]<x )
        {
            s=mid+1;
            ret=mid;
        }
        else
        {
            t=mid-1;
        }
    }
    return ret;
}
void find_idx(int x, int &s, int &t)
{
    s=bin_search(0,99999,x);
    if ( num[s]==x)
    {
        t=s;
    }
    else
    {
        t=s+1;
    }
}
void makeprime()
{
    total=-1;
    memset(isprime, true, sizeof(isprime) );
    for (int i=2; i<=1299709; ++i)
    {
        if ( isprime[i] )
        {
            num[ ++total ]=i;
        }
        for (int j=0; j<=total&& i*num[j]<=1299709; ++j)
        {
            isprime[i*num[j]]=false;
            if ( i%num[j]==0 )
            {
                break;
            }
        }
    }
}
int main(int argc, char *argv[])
{
    makeprime();
    while ( scanf("%d", &n) && n!=0 )
    {
        find_idx(n,s,t);
        printf("%d/n", num[t]-num[s]);
        
    }
    return 0;
}