我正在尝试使用 Eratosthenes 的分段筛解决问题PRIME1 。我的程序在正常筛子上正常工作，最高可达NEW_MAX. n > NEW_MAX但是在分段筛分发挥作用的情况下存在一些问题。在这种情况下，它只会打印所有数字。以下是包含相关测试用例的代码链接：http: //ideone.com/8H5lK#view_edit_box
/* segmented sieve */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIMIT 1000000000 //10^9
#define NEW_MAX 31623 /*SQUARE ROOT OF 1000000000*/
#define MAX_WIDTH 100000 //10^5
char flags[NEW_MAX+100]; /*TO PREVENT SEGMENTATION FAULT*/
void initialise(char flagarr[], long int n) //initialise all elements to true from 1 to n
{
long int i;
for (i = 1; i <= n; i++)
flagarr[i] = 't';
}
void sieve(unsigned long long m, unsigned long long n, char seg_flags[])
{
unsigned long long p, i, limit;
if (m == 1)
seg_flags[1] = 'f';
/*Seperate inner loop for p=2 so that evens are not iterated*/
for (i = 4; i >= m && i <= n; i += 2)
{
seg_flags[i-m+1] = 'f';
}
if (seg_flags == flags)
limit = NEW_MAX;
else
limit = sqrt(n);
for (p = 3; p <= limit+1; p += 2) //initial p+=2 bcoz we need not check even
{
if (flags[p] == 't')
{
for (i = p*p; i >= m && i <= n; i += p) //start from p square since under it would have been cut
seg_flags[i-m+1] = 'f'; /*p*p, p*p+p, p*p + 2p are not primes*/
}
}
}
void print_sieve(unsigned long long m,unsigned long long n,char flagarr[])
{
unsigned long long i;
if (flags == flagarr) //print non-segented sieve
{
for (i = m; i <= n; i++)
if (flagarr[i] == 't')
printf("%llu\n", i);
}
else
{
//print segmented
for (i = m; i <= n; i++)
if (flagarr[i-m+1] == 't')
printf("%llu\n", i);
}
}
int main()
{
unsigned long long m, n;
int t;
char seg_flags[MAX_WIDTH+100];
/*setting of flags for prime nos. by sieve of erasthromas upto NEW_MAX*/
initialise(flags, NEW_MAX);
flags[1] = 'f'; /*1 is not prime*/
sieve(1, NEW_MAX, flags);
/*end of initial sieving*/
scanf("%d", &t);
while (t--)
{
scanf("%llu %llu", &m, &n);
if (n <= NEW_MAX)
print_sieve(m, n, flags); //NO SEGMENTED SIEVING NECESSARY
else if (m > NEW_MAX)
{
initialise(seg_flags, n-m+1); //segmented sieving necessary
sieve(m, n, seg_flags);
print_sieve(m, n, seg_flags);
}
else if (m <= NEW_MAX && n > NEW_MAX) //PARTIAL SEGMENTED SIEVING NECESSARY
{
print_sieve(m, NEW_MAX, flags);
/*now lower bound for seg sieving is new_max+1*/
initialise(seg_flags, n-NEW_MAX);
sieve(NEW_MAX+1, n, seg_flags);
print_sieve(NEW_MAX+1, n, seg_flags);
}
putchar('\n');
}
system("pause");
return 0;
}
更新：感谢您的回复丹尼尔。我实施了一些你的建议，我的代码现在产生了正确的输出：-
/*segmented sieve*/
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX_LIMIT 1000000000 /*10^9*/
#define NEW_MAX 31623 /*SQUARE ROOT OF 1000000000*/
#define MAX_WIDTH 100000 /*10^5*/
int flags[NEW_MAX+1]; /*TO PREVENT SEGMENTATION FAULT goblal so initialised to 0,true*/
void initialise(int flagarr[],long int n)
/*initialise all elements to true from 1 to n*/
{
long int i;
for(i=3;i<=n;i+=2)
flagarr[i]=0;
}
void sieve(unsigned long m,unsigned long n,int seg_flags[])
{
unsigned long p,i,limit;
/*Seperate inner loop for p=2 so that evens are not iterated*/
if(m%2==0)
i=m;
else
i=m+1;
/*i is now next even > m*/
for(;i<=n;i+=2)
{
seg_flags[i-m+1]=1;
}
if(seg_flags==flags)
limit=NEW_MAX;
else
limit=sqrt(n);
for(p=3;p<=limit+1;p+=2) /*initial p+=2 bcoz we need not check even*/
{
if(flags[p]==0)
{
for(i=p*p; i<=n ;i+=p)
/*start from p square since under it would have been cut*/
{
if(i<m)
continue;
seg_flags[i-m+1]=1;
/*p*p, p*p+p, p*p + 2p are not primes*/
}
}
}
}
void print_sieve(unsigned long m,unsigned long n,int flagarr[])
{
unsigned long i;
if(m<3)
{printf("2\n");m=3;}
if(m%2==0)
i=m+1;
else
i=m;
if(flags==flagarr) /*print non-segented sieve*/
{
for(;i<=n;i+=2)
if(flagarr[i]==0)
printf("%lu\n",i);
}
else {
//print segmented
for(;i<=n;i+=2)
if(flagarr[i-m+1]==0)
printf("%lu\n",i);
}}
int main()
{
unsigned long m,n;
int t;
int seg_flags[MAX_WIDTH+100];
/*setting of flags for prime nos. by sieve of erasthromas upto NEW_MAX*/
sieve(1,NEW_MAX,flags);
/*end of initial sieving*/
scanf("%d",&t);
while(t--)
{
scanf("%lu %lu",&m,&n);
if(n<=NEW_MAX)
print_sieve(m,n,flags);
/*NO SEGMENTED SIEVING NECESSARY*/
else if(m>NEW_MAX)
{
initialise(seg_flags,n-m+1);
/*segmented sieving necessary*/
sieve(m,n,seg_flags);
print_sieve(m,n,seg_flags);
}
else if(m<=NEW_MAX && n>NEW_MAX)
/*PARTIAL SEGMENTED SIEVING NECESSARY*/
{
print_sieve(m,NEW_MAX,flags);
/*now lower bound for seg sieving is new_max+1*/
initialise(seg_flags,n-NEW_MAX);
sieve(NEW_MAX+1,n,seg_flags);
print_sieve(NEW_MAX+1,n,seg_flags);
}
putchar('\n');
}
system("pause");
return 0;
}
但是我下面的筛子功能进一步考虑了您的其他建议会产生不正确的输出：-
void sieve(unsigned long m,unsigned long n,int seg_flags[])
{
unsigned long p,i,limit;
p=sqrt(m);
while(flags[p]!=0)
p++;
/*we thus get the starting prime, the first prime>sqrt(m)*/
if(seg_flags==flags)
limit=NEW_MAX;
else
limit=sqrt(n);
for(;p<=limit+1;p++) /*initial p+=2 bcoz we need not check even*/
{
if(flags[p]==0)
{
if(m%p==0) /*to find first multiple of p>=m*/
i=m;
else
i=(m/p+1)*p;
for(; i<=n ;i+=p)
/*start from p square since under it would have been cut*/
{
seg_flags[i-m+1]=1;
/*p*p, p*p+p, p*p + 2p are not primes*/
}
}
}
}