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