我正在尝试使用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("%llun", i); } else { //print segmented for (i = m; i <= n; i++) if (flagarr[i-m+1] == 't') printf("%llun", 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("2n");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("%lun",i); } else { //print segmented for(;i<=n;i+=2) if(flagarr[i-m+1]==0) printf("%lun",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似乎澄清了一些主要的问题点。
如果您有兴趣查看有关此素数问题的更简洁的代码/解释,请查看:
以上就是c/c++开发分享使用eratosthenes筛子的Spoj PRIME1(在C中)相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559612.html