你的位置:主页 > 乐视 >

【ACM】求素数的多种方法

2020-07-16 | 人围观

  素数:质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。

  下面给出求素数的几种不同的算法。

  假设我们给定一位数N,现在判断这个数字是不是素数。

  方法一:

  从2开始遍历到N-1 。

  这是一种非常慢的方法。

  方法二:

  对上述的方案进行稍微的优化

  因为一个数N=a*b,则只需找出a,b中的较小值就可以,而较小值的最大上限不会超过sqrt(N)。

  方法三:

  遍历从2到N的平方根下每一个素数,但是如果N很大,素数表的构建就会非常复杂。因此我们可以选择构建动态素数表,但是效率依然会很低。

  1:试除法:试除sqrt(N)以内的素数

  2:筛选法:(下面给出两个链接)

  Sieve of Eratosthenes

  Euler‘s Sieve

  方法四:

  费马小定理 + 快速幂运算

  对于两个互质(两个正整数只有公约数1时)的素数n和p,必有n^(p-1) % p=1 。考虑到在运算高次幂运算时候可能会发生上溢,所以采用快速幂取模算法。

  以上是快速幂取模的算法

  但是例如数字29341,等于13* 37*61,显然是一个合数,但是被判断为了素数,所以这种策略是一种不可靠的策略。这一类数字叫做卡米歇尔数。卡米歇尔数和素数非常相似,都满足了费马小定理,因此称之为伪素数。随着数越来越大,卡米歇尔数变得越来越少,1至10^17有585 355个卡米歇尔数。

  方法五:

  拉宾米勒测试(目前未知最快的判断素数的方法,没有之一)

标签:
Top