使用eratosthenes筛子的Spoj PRIME1（在C中）
我正在尝试使用Eratosthenes的分段筛来解决问题PRIME1 。 我的程序可以正常筛选，达到NEW_MAX 。 但是在n > NEW_MAX情况下存在一些问题，其中分段筛分发挥作用。 在这种情况下，它只打印所有数字。 以下是包含相关测试用例的代码的链接： http ： //ideone.com/8H5lK#view_edit_box
/* segmented sieve */ #include #include #include #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 = 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 = 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) { 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) //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 #include #include #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 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(nNEW_MAX) { initialise(seg_flags,n-m+1); /*segmented sieving necessary*/ sieve(m,n,seg_flags); print_sieve(m,n,seg_flags); } else if(mNEW_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; }
但我的筛选function进一步考虑到你的其他建议产生不正确的输出： –
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=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*/ } } } }
你的问题是
for (i = 4; i >= m && i <= n; i += 2) for (i = p*p; i >= m && i <= n; i += p)
如果范围的下限为4或更小，则只消除2的倍数，并且只消除大于sqrt(m)的素数倍数。 从循环条件中删除i >= m部分并将其替换为if (i < m) { continue; } 在循环体中（更好的是，直接计算p的第一个倍数不小于m并完全避免该条件）。
而不是使用't'和'f'作为标志，使用1和0作为DMR意图，这将被更好地理解。
重新更新：这个
/*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)
如果m == 2会伤害你。 如果m == 2 ，则必须以i = 4开头。
关于
unsigned long p,i,limit; p=sqrt(m); while(flags[p]!=0) p++; /* snip */ for(;p<=limit+1;p++)
你好像误解了我，“你只消除了大于sqrt(m)的素数倍数”并不意味着你不需要消除多个较小的素数，这意味着你的初始版本没有，这几乎导致了范围内的数字未消除。 你应该用p = 2开始外循环 - 或者为2的倍数单独传递并用3开始循环，将p递增2，并在p*p和p*p最大值处开始内循环p不小于m 。 你的后者的代码是有效的，所以把它包装成一个
if ((i = p*p) < m) { /* set i to smallest multiple of p which is >= m */ }
会工作（你可以让它更快一点，避免分支，只使用一个分区，但差异将是微不足道的）。
最后，你选择0和1表示的是非常规的，这是C，所以0在条件中评估为false，其他一切都为true，因此规范替换将是't' -> 1和'f' -> 0并且在这样的上下文中，数组条目是标志，可以检查
if (flags[p]) // instead of: if (flags[p] != 0) if (!flags[p]) // instead of: if (flags[p] == 0)
也没有必要将数组类型从char[]更改为int[] ， char也是一个整数类型，因此0和1是非常精细的char值。 arrays类型的选择具有性能影响。 一方面， int -sized加载和存储通常比字节大小快，因此有利于int flags[]甚至long int flags[]用于字大小的读写。 另一方面，使用较小的char flags[]可以获得更好的缓存局部性。 通过每个标志使用一个位，您将获得更好的缓存局部性，但这会使读取/设置/清除标志仍然更慢。 产生最佳性能的因素取决于筛网的结构和尺寸。
Daniel Fischer似乎澄清了一些主要的问题点。
如果您有兴趣查看有关此素数问题的更简洁的代码/解释，请查看：
http://www.swageroo.com/wordpress/spoj-problem-2-prime-generator-prime1/