C＋＋中筛法求素去素

点击联系发帖人 时间：2019-02-02 08:56

素筛法

这里主要说一下素数筛法求素該方法可以快速的选取出1~N数字中的所有素数。时间复杂度远小于O(N*sqrt(N))

方法为：从2开始往后所有素数的倍数都不是素数。最后剩下的数都是素數

再说说欧拉公式，用来解决所有小于n中的数字有多少个与n互质用Ψ(n)表示。

注意：关于数论的题很容易超过int类型的范围多考虑用long long类型。

}

你对这个回答的评价是

数组定義时的长度是从0开始计算的 即0-100 一共有101个数所以要定义为101，但本题中没有使用下标0所以将算法稍作修改，让0-99 对应 数值1-100的话长度定义可以用100（一般不要在这里纠结太多没什么意义）

bool 只占一个字节
int 一般占4个字节
你喜欢用int也可以

好的，谢谢我还有最后一个问题。
int main中为什么还有那一串代码…

那个括号我可以空着吧

那个括号里你写的是什么意思

本回答被提问者和网友采纳

你对这个回答的评价是？

}

自己没事,写的一个程序,筛法求素嘚原理:在n(n为求素数的范围)以内的数中,把2的倍数都去掉,再把3的倍数都去掉,如此,依次把第一个没有去掉数的倍数去掉,注意这个数本身不去掉.最後没被去掉的为所有的素数

//一共有三个算法A B A2　其中A B　很慢
//A2是改进型，速度很快如不往屏幕输出　１亿内的质数在1.3秒内求出。
//B是用的是位操作用内存少　因为没有优化，所以速度慢class Prime

}