素数筛C++实现及应用

埃拉托斯特尼筛法(sieve of Eratosthenes ) 是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数,我们先找出sqrt(n)内的所有素数p1pk,其中k = sqrt(n),依次剔除Pi的倍数,剩下的所有数都是素数。

具体操作如上述 图片所示。

C++实现

整除问题

给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。

输入描述

输出描述

示例1

输入

输出

代码

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注