主题:一个程序片段,求牛人指教
一个大程序中的小片段
现在已知[1,x的1/3次方]中的素数表。存放在一个数组中(*gpPTable),可以直接调用。
已知素数表中素数的个数为a
对于区间[1,x的2/3次方],按照长度为x的1/3次方分区间,第k个区间表示如下:
[(k-1)N,kN],区间中元素用(k-1)N+L表示
筛选:
对于此区间中的每个数,用gpPTable[0]筛,筛到的话记下此数对应的L值,并执行一个循环(上下文的,不用管)
然后前进到gpPTable[1],……
当k区间被筛完后,前进到k+1区间
我现在的程序速度比较慢,所以希望牛人可以指点一下,但是简单的求余可能不行,希望有一个完全不同的思路来做。
for(k=1;k<=N2_N;k++) //N2_N是定义的区间个数
{
for(j=1;j<a;j++)
{
l=gpPTable[j-1]-((k-1)*N)%gpPTable[j-1]; //直接计算第一个被筛出的l值
while(l<=N&&flag[l-1]==0)//flag数组长度为区间长度,是表示区间中某个数是否被筛过的,先全置1,每筛出一个数对应的就置为0
{
l+=gpPTable[j-1];
} //找到尚未被筛出的l值
if(j==1)
delta=2;
else
delta=gpPTable[j-1]<<1; //跳跃量,由于2倍的已在上一循环中被筛过
//跳跃筛选
for(notel=l; notel<=N; notel+=delta)
{ //下面的可以不管,就是找到L后用这个L执行一个数组的更新,关键是如何快速找到L
*****************************************************************************
if(flag[notel-1])
{
temp = notel-1; //用于提高速度的中间变量
for(i=0;i<log2N;i++)
{
parrayA[i][temp+1]--;
temp>>=1;
}
flag[notel-1]=0;//筛过后置为0
}
}
}
*****************************************************************************
另一个想法是对k=1单独处理,然后对k>=2
for(j=1;j<a;j++) //pFAITable的第二个参数的变化
{
if(gpPTable[j-1]*gpPTable[j-1]<=k*N)
{//只需要k*N开平方以内的素数去筛就可以
l=gpPTable[j-1]-(k*N-N)%gpPTable[j-1];
while(l<=N&&flag[l-1]==0)
{
l+=gpPTable[j-1];
}
if(j==1)
delta=2;
else
delta=gpPTable[j-1]<<1; //跳跃量,由于2倍的已在上一循环中被筛过
//跳跃筛选
for(notel=l-1; notel<N; notel+=delta)
{
if(flag[notel])
{
temp = notel; //用于提高速度的中间变量
for(i=0;i<log2N;i++)
{
parrayA[i][temp+1]--;
temp>>=1;
}
flag[notel]=0; //筛过后置为0
}
}
}
}
请教还有没有谁可以想出完全不同的思路??
谢谢!
现在已知[1,x的1/3次方]中的素数表。存放在一个数组中(*gpPTable),可以直接调用。
已知素数表中素数的个数为a
对于区间[1,x的2/3次方],按照长度为x的1/3次方分区间,第k个区间表示如下:
[(k-1)N,kN],区间中元素用(k-1)N+L表示
筛选:
对于此区间中的每个数,用gpPTable[0]筛,筛到的话记下此数对应的L值,并执行一个循环(上下文的,不用管)
然后前进到gpPTable[1],……
当k区间被筛完后,前进到k+1区间
我现在的程序速度比较慢,所以希望牛人可以指点一下,但是简单的求余可能不行,希望有一个完全不同的思路来做。
for(k=1;k<=N2_N;k++) //N2_N是定义的区间个数
{
for(j=1;j<a;j++)
{
l=gpPTable[j-1]-((k-1)*N)%gpPTable[j-1]; //直接计算第一个被筛出的l值
while(l<=N&&flag[l-1]==0)//flag数组长度为区间长度,是表示区间中某个数是否被筛过的,先全置1,每筛出一个数对应的就置为0
{
l+=gpPTable[j-1];
} //找到尚未被筛出的l值
if(j==1)
delta=2;
else
delta=gpPTable[j-1]<<1; //跳跃量,由于2倍的已在上一循环中被筛过
//跳跃筛选
for(notel=l; notel<=N; notel+=delta)
{ //下面的可以不管,就是找到L后用这个L执行一个数组的更新,关键是如何快速找到L
*****************************************************************************
if(flag[notel-1])
{
temp = notel-1; //用于提高速度的中间变量
for(i=0;i<log2N;i++)
{
parrayA[i][temp+1]--;
temp>>=1;
}
flag[notel-1]=0;//筛过后置为0
}
}
}
*****************************************************************************
另一个想法是对k=1单独处理,然后对k>=2
for(j=1;j<a;j++) //pFAITable的第二个参数的变化
{
if(gpPTable[j-1]*gpPTable[j-1]<=k*N)
{//只需要k*N开平方以内的素数去筛就可以
l=gpPTable[j-1]-(k*N-N)%gpPTable[j-1];
while(l<=N&&flag[l-1]==0)
{
l+=gpPTable[j-1];
}
if(j==1)
delta=2;
else
delta=gpPTable[j-1]<<1; //跳跃量,由于2倍的已在上一循环中被筛过
//跳跃筛选
for(notel=l-1; notel<N; notel+=delta)
{
if(flag[notel])
{
temp = notel; //用于提高速度的中间变量
for(i=0;i<log2N;i++)
{
parrayA[i][temp+1]--;
temp>>=1;
}
flag[notel]=0; //筛过后置为0
}
}
}
}
请教还有没有谁可以想出完全不同的思路??
谢谢!