关于素数的数列,高手进!a1 = 1a2 = 3a3 = 6a4 = 11a[n] - a[n - 1]是一个递增的素数序列如果a[n] > 10000, a[n] = a[n] % 10000;input noutput a[n]下面这个解法我看不懂,请高手讲解,谢谢!#include #include #define N 1000001 #define MOD 10000 long p[50001]; bool prime[N]; long out[50001]; void get_out() { long i,num=0,j,k; memset(prime,0,sizeof(prime)); out[0]=1; for(i=2;i
问题描述：
关于素数的数列,高手进!
a1 = 1
a2 = 3
a3 = 6
a4 = 11
a[n] - a[n - 1]是一个递增的素数序列
如果a[n] > 10000, a[n] = a[n] % 10000;
input n
output a[n]
下面这个解法我看不懂,请高手讲解,谢谢!
#include
#include
#define N 1000001
#define MOD 10000
long p[50001];
bool prime[N];
long out[50001];
void get_out()
{
long i,num=0,j,k;
memset(prime,0,sizeof(prime));
out[0]=1;
for(i=2;i
答
这个算法没什么难懂的啊,无非是利用了筛法来建素数数组而已.
筛法的原理是：假设要求从2到n之间所有的素数,可以选建一个长度为n-1的数组,初始全设为0,表示目前所有的数都是素数.然后从2开始向后遍历,每遇到一个素数(在数组中对应值为0),就将其的整数倍在数组中的对应值设为1.这样的话,第一次就删掉了所有的2的倍数,第二次删掉3的倍数,第三次删掉5的倍数（4的倍数在第一次删2的倍数时已经删掉了）,第四次删掉7的倍数（6的倍数已经在删2,3的倍数时删掉了）.以此类推,直到遍历结束,这时候,所有的合数已经都被筛选掉了.
程序中的
for(j=0;j=N)
break;
prime[k]=1;
}
这段,就是筛法的核心代码了.