3
我试图解决问题PRIME1使用Eratosthenes分割筛。我的程序可以正常使用正常筛网，最高可达NEW_MAX。但是在分段筛分发挥作用的情况下，有一些问题n > NEW_MAX。在这种情况下，它只是打印所有的数字。这里是链接到代码相关的测试用例：http://ideone.com/8H5lK#view_edit_boxSpoj PRIME1使用Eratosthenes筛（在C）
/* 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;
}
更新：感谢您的FR响应丹尼尔。我实现了一些乌尔建议，我的代码现在产生正确的输出： -
/*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*/
}
}
}
}
选择的代码和使用Ctrl-K – 2012-02-20 13:54:43