题目
关于素数的数列,高手进!
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
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
提问时间:2021-01-21
答案
这个算法没什么难懂的啊,无非是利用了筛法来建素数数组而已.
筛法的原理是:假设要求从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;
}
这段,就是筛法的核心代码了.
筛法的原理是:假设要求从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;
}
这段,就是筛法的核心代码了.
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1我需要一篇以"代价"为话题的作文.我是一个女生,注意文章情节.请帮帮忙!
- 20.833 6分之5 八五折 85.1 从小到大排
- 3一辆汽车从甲地开往乙地,每小时行60千米,2.5小时后,已行的路程与未行的路程比是2:3到达乙地还需多少小时
- 4never frown,even when you are sad.什么意思
- 5用Maple算矩阵的特征值.如果我在开头给pi赋值,最后结果是复数;如果在开头不赋值,算出来是实数.为什么
- 6我国商业银行个人理财业务现状与发展对策
- 7问题.在伏安法测小灯泡的电功率的实验中,
- 8怎么知道一篇文章是否被SCI收录?检索号又在哪里查呢?
- 9用0123456789可以组成多少4位数
- 10求|x-1|+2|x-2|+3|x-3|+4|x-4|+......+2011|x-2011|的最小值?
热门考点
- 1如图所示,AB和BC是由同种材料制成的长度相同、横截面积不同的两段导体,将它们串联后连入电路中.比较通过它们的电流的大小_(选填“IAB<IBC”“IAB=IBC”或“IAB>IB“)
- 2一件商品按成本加30%出售,售价156元,若这件商品后来又降价5%卖出,则这件商品的利润率是多少?
- 3英文翻译!这个问题问出了古今中外多少才子佳人心中的无解的疑惑.
- 4梧桐树:作用、形状
- 5When summer comes ,the weather ________(be) hot.
- 6“若尘”是什么意思
- 7三角形ABC中,AB=AC=5,BC=6,P在AB上,Q在BC,且AP=BQ=x,x为何值时PQ=2AP
- 8x×【(x÷2)的平方】 ×3.14=6.28这个方程怎么解
- 9All Money on My Home请问中文是什么意思?
- 10在线急等一道英语完形填空题~