Spoj PRIME1埃拉托色尼的使用筛（C语言） [英] Spoj PRIME1 using sieve of eratosthenes (in C)
问题描述
我试图解决使用埃拉托色尼的分段筛问题 PRIME1 。我的程序与正常筛即达 NEW_MAX 正常工作。但有一些问题，案件 N'GT; NEW_MAX ，其中分段筛分用武之地。在这种情况下，仅仅是打印所有的数字。这里是链接到code。与相关的测试案例： http://ideone.com/8H5lK#view_edit_box
/ *分段筛* /
＃包括LT＆;＆math.h中GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃定义MAX_LIMIT十亿// 10 ^ 9
10亿的#define NEW_MAX 31623 / *平方根* /
＃定义MAX_WIDTH 100000 // 10 ^ 5
字符标志[NEW_MAX + 100]; / * TO preVENT分段错误* /无效的initialise（CHAR flagarr []，长整型N）//初始化为true的所有元素从1到n
{
长INT I;
对于（i = 1; I＆LT; = N;我++）
flagarr [I] ='T';
}无效筛（无符号长长男，无符号长N久，焦炭seg_flags []）
{
无符号长长P，I，限制;
如果（M == 1）
seg_flags [1] = f的;
/ *独立内环对于p = 2，使得找齐不迭代* /
对于（i = 4; I＆GT; = M＆放大器;＆安培; I＆LT; = N，I + = 2）
{
seg_flags [I-M + 1] = f的;
}
如果（seg_flags ==标志）
极限= NEW_MAX;
其他
极限=开方（N）;
为（P = 3; P＆LT; =极限+ 1; P + = 2）//初始P + = 2 bcoz我们不需要检查连
{
如果（标志[P] =='T'）
{
对（我= P * P，I＆GT; = M＆放大器;＆安培; I＆LT; = N，I + = P）//从对从头做起，因为根据它会被切断
seg_flags [I-M + 1] = f的; / * P * P，P * P + P，P * P + 2P不素数* /
}
}
}无效print_sieve（无符号长长男，无符号长N久，焦炭flagarr []）
{
无符号长长我;
如果（标志== flagarr）//打印非segented筛
{
对于（i =米; I＆LT; = N;我++）
如果（flagarr [I] =='T'）
的printf（％LLU \\ n，I）;
}
其他
{
//打印分割
对于（i =米; I＆LT; = N;我++）
如果（flagarr〔Ⅰ-M + 1] =='T'）
的printf（％LLU \\ n，I）;
}
}诠释的main（）
{
无符号长长的M，N;
INT吨;
焦炭seg_flags [MAX_WIDTH + 100];
/ *标志的黄金号的设置。通过erasthromas高达NEW_MAX筛* /
初始化（旗，NEW_MAX）;
标志[1] = f的; / * 1不是素数* /
筛（1，NEW_MAX，标志）;
/ *初始筛分结束* /
scanf函数（％d个，＆amp; T公司）;
而（T--）
{
scanf函数（％LLU％LLU，＆安培;男，＆安培; N）;
如果（N＆LT; = NEW_MAX）
print_sieve（M，N，旗）; //没有基于分段筛分必要
否则，如果（M＆GT; NEW_MAX）
{
初始化（seg_flags，N-M + 1）; //必要的分段筛分
筛（M，N，seg_flags）;
print_sieve（M，N，seg_flags）;
}
否则，如果（M＆LT; = NEW_MAX和放大器;＆安培; N＆GT; NEW_MAX）//局部基于分段筛分必要
{
print_sieve（男，NEW_MAX，旗）;
/ *现在下限为赛格筛分new_max + 1 * /
初始化（seg_flags，正NEW_MAX）;
筛（NEW_MAX + 1中，n，seg_flags）;
print_sieve（NEW_MAX + 1，N，seg_flags）;
}
的putchar（'\\ n'）;
}
系统（暂停）;
返回0;
}
更新：感谢您的FR响应丹尼尔。我实现了一些乌尔建议，我的code现在产生正确的输出： -
/ *分段筛* /
＃包括LT＆;＆MATH.H GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃定义MAX_LIMIT 10亿/ * 10 ^ 9 * /
10亿的#define NEW_MAX 31623 / *平方根* /
＃定义MAX_WIDTH 100000 / * 10 ^ 5 * /
诠释标志[NEW_MAX + 1〕; / * TO preVENT分段故障goblal所以初始化为0，真正的* /无效的initialise（INT flagarr []，长整型N）
/ *初始化为true，所有的元素从1到n * /
{
长INT I;
对于（i = 3; I＆LT; = N，I + = 2）
flagarr [I] = 0;
}无效筛（无符号长男，无符号长N，INT seg_flags []）
{ 无符号长P，I，限制; / *独立内环对于p = 2，使得找齐不迭代* /
如果（M 2％== 0）
I =米;
其他
I = M + 1;
/ *我现在是一个偶数＆GT; M * /
对于（; I＆LT; = N，I + = 2）
{ seg_flags [I-M + 1] = 1; }
如果（seg_flags ==标志）
极限= NEW_MAX;
其他
极限=开方（N）;
为（P = 3; P＆LT; =极限+ 1; P + = 2）/ *初始P + = 2 bcoz我们不需要检查甚至* /
{
如果（标志[P] == 0）
{
对（我= P * P，I＆LT; = N，I + = P）
/ *从对从头做起，因为根据它就会被切断* /
{
如果（ⅰ＆所述M）
继续;
seg_flags [I-M + 1] = 1;
/ * P * P，P * P + P，P * P + 2P不素数* / }
}
}
}无效print_sieve（无符号长男，无符号长N，INT flagarr []）
{
无符号长我;
如果（M 3;）
{printf的（2 \\ n）; M = 3;}
如果（M 2％== 0）
I = M + 1;
其他
I =米;
如果（标志== flagarr）/ *打印非segented筛* /
{
对于（; I＆LT; = N，I + = 2）
如果（flagarr [I] == 0）
的printf（％鲁\\ n，I）;
}
其他{
//打印分割 对于（; I＆LT; = N，I + = 2）
如果（flagarr〔Ⅰ-M + 1] == 0）
的printf（％鲁\\ n，I）;
}}诠释的main（）
{
无符号长M，N;
INT吨;
诠释seg_flags [MAX_WIDTH + 100];
/ *标志的黄金号的设置。通过erasthromas高达NEW_MAX筛* /
筛（1，NEW_MAX，标志）;
/ *初始筛分结束* /
scanf函数（％d个，＆amp; T公司）;
而（T--）
{
scanf函数（％鲁％录，＆安培;男，＆安培; N）;
如果（N＆LT; = NEW_MAX）
print_sieve（M，N，旗）;
/ * NO基于分段筛分必要* /
否则，如果（M＆GT; NEW_MAX）
{
初始化（seg_flags，N-M + 1）;
/ *分段筛分必要* /
筛（M，N，seg_flags）;
print_sieve（M，N，seg_flags）;
}
否则，如果（M＆LT; = NEW_MAX和放大器;＆安培; N＆GT; NEW_MAX）
/ *局部基于分段筛分必要* /
{
print_sieve（男，NEW_MAX，旗）;
/ *现在下限为赛格筛分new_max + 1 * /
初始化（seg_flags，正NEW_MAX）;
筛（NEW_MAX + 1中，n，seg_flags）;
print_sieve（NEW_MAX + 1，N，seg_flags）;
}
的putchar（'\\ n'）;
}
系统（暂停）;
返回0;
}
但我的筛子下面的功能进一步考虑到乌拉圭回合的其他建议产生不正确的输出： -
无效筛（无符号长男，无符号长N，诠释seg_flags []）
{ 无符号长P，I，限制;
p值= SQRT（米）;
而（标志[P]！= 0）
p ++;
/ *我们从而得到首发总理，第一任＆GT;的sqrt（M）* / 如果（seg_flags ==标志）
极限= NEW_MAX;
其他
极限=开方（N）;
为（; P＆LT; =极限+ 1，P ++）/ *初始P + = 2 bcoz我们不需要检查甚至* /
{
如果（标志[P] == 0）
{
如果（M％P == 0）/ *找到P＆GT的第一多个= M * /
I =米;
其他
I =（M / P + 1）* P; 对于（; I＆LT; = N，I + = P）
/ *从对从头做起，因为根据它就会被切断* /
{ seg_flags [I-M + 1] = 1;
/ * P * P，P * P + P，P * P + 2P不素数* / }
}
}
}
您的问题是
为（I = 4; I＆GT; = M＆放大器;＆安培; I＆LT; = N，I + = 2）
对（我= P * P，I＆GT; = M＆放大器;＆安培; I＆LT; = N，I + = P）
您只会消除2的倍数因此如果范围的较低端是4个或更少，而你只消除素数的倍数比的sqrt（M）。从循环条件= M 部分并将其替换为一个如果（I＆LT; M）中删除 I＆GT {继续; } 在循环体（更好，计算 P 第一多个不超过 M 直接，避免病情完全）。
和，而不是使用'T'和'F'作为标志，使用 1 和 0 为DMR预期，将被更好地理解。
重新更新：此
/ *独立内环为P = 2这样找齐不重复* /
如果（M 2％== 0）
I =米;
其他
I = M + 1;
/ *我现在是一个偶数＆GT; M * /
对于（; I＆LT; = N，I + = 2）
会伤害你，如果米== 2 。如果米== 2 ，你必须用启动I = 4 。
关于
无符号长P，I，限制;
p值= SQRT（米）;
而（标志[P]！= 0）
p ++;
/ * * SNIP /
为（; P＆LT; =极限+ 1，P ++）
看来你误解了我，你只消除开方比大素数的倍数（M）并不意味着你不必消除小素数的倍数，这意味着你的最初版本没有，这导致几乎范围内所有数字没有消除。你应该开始以 P = 2 - 或有2倍数单独的过程，并启动循环3，递增 P <外环/ code> 2，在 p * p 的更大 p 不超过 M 。您code后者的作品，所以其包装在
IF（（I = P * P）LT; M）{
/ *设置我到最小P的的制造＆gt多个= M * /
}
将工作（你可以把它快一点，避免了分公司，并只使用一个师，但差异将是微不足道的）。
最后，你的就是你能0重新present选择1是明显不规范，这是C，所以0计算结果为假的条件，一切为真，那么规范的替代将是'T' - ＆GT; 1 和'F' - ＆GT; 0 ，并在这样的背景下，数组项标志，一会检查
IF（标志[P]）//而不是：如果（！旗帜[P] = 0）
如果（！旗帜[P]）//代替：如果（标志[P] == 0）
也没有必要从的char [] 改变数组类型 INT [] ，字符是一个整数类型了，所以0和1是完全没有字符值。类型为阵列的选择会对性能产生影响。在一方面， INT -sized负载和存储通常快于字节大小，这样将有利于 INT标志[] 甚至长整型标志[] 对于字大小的读取和写入。在另一方面，与较小的标记的char [] 您获得更好的高速缓存位置。你会得到更好的缓存局部用标志每一个比特，但是这将使得读/设置/清除标志仍然较慢。什么产生最佳性能取决于筛的结构和大小。
I'm trying to solve the problem PRIME1 using segmented sieve of Eratosthenes. My program works correctly with the normal sieve that is up to NEW_MAX. But there is some problem with cases n > NEW_MAX, where segmented sieving comes into play. In such cases it merely prints all the numbers. Here is the link to the code with relevant test cases: 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;
}
Update: Thanks fr your response Daniel. I implemented some of ur suggestions, my code now produces correct output :-
/*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;
}
but my sieve function below further taking into account ur other suggestions produces incorrect output:-
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*/
}
}
}
}
Your problem is
for (i = 4; i >= m && i <= n; i += 2)
for (i = p*p; i >= m && i <= n; i += p)
You only ever eliminate the multiples of 2 as such if the lower end of the range is 4 or less, and you only eliminate multiples of primes larger than sqrt(m). Remove the i >= m part from the loop condition and replace it with an if (i < m) { continue; } in the loop body (better, calculate the first multiple of p not less than m directly and avoid that condition completely).
And instead of using 't' and 'f' as flags, use 1 and 0 as DMR intended, that will be understood better.
Re update: This
/*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)
will hurt you if m == 2. If m == 2, you must start with i = 4.
Concerning
unsigned long p,i,limit;
p=sqrt(m);
while(flags[p]!=0)
p++;
/* snip */
for(;p<=limit+1;p++)
it seems you misunderstood me, "and you only eliminate multiples of primes larger than sqrt(m)" doesn't mean you needn't eliminate multiples of smaller primes, it means that your initial version didn't, which resulted in almost all numbers in the range not eliminated. You should start the outer loop with p = 2 -or have a separate pass for the multiples of 2 and start that loop with 3, incrementing p by 2, and start the inner loop at the larger of p*p and the smallest multiple of p not less than m. Your code for the latter works, so wrapping it in an
if ((i = p*p) < m) {
/* set i to smallest multiple of p which is >= m */
}
would work (you can make it a bit faster avoiding a branch and using only one division, but the difference will be minuscule).
Finally, your choice of what you represent by 0 and 1 is uncanonical, this is C, so 0 evaluates to false in conditions and everything else to true, so the canonical replacement would have been 't' -> 1 and 'f' -> 0 and in contexts like this, where the array entries are flags, one would check
if (flags[p]) // instead of: if (flags[p] != 0)
if (!flags[p]) // instead of: if (flags[p] == 0)
also there's no need to change the array types from char[] to int[], char is an integer type too, so 0 and 1 are perfectly fine char values. The choice of type for the arrays has performance implications. On the one hand, int-sized loads and stores are typically faster than byte-sized, so that would favour int flags[] or even long int flags[] for word-sized reads and writes. On the other hand, with the smaller char flags[] you get better cache locality. You would get even better cache locality with using a single bit per flag, but that would make reading/setting/clearing flags still slower. What yields the best performance depends on the architecture and size of the sieves.
这篇关于Spoj PRIME1埃拉托色尼的使用筛（C语言）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
