检查数字是否为素数的最佳算法是什么？
Ara*_*raK 148 algorithm math primes data-structures
只是我正在寻找的一个例子:我可以用一点代表每个奇数,例如对于给定的数字范围(1,10),从3开始:
__PRE__
以下字典可以挤得更对吗？我可以通过一些工作来消除五的倍数,但是以1,3,7或9结尾的数字必须在位数组中存在.希望这能澄清我想要的东西.
我正在寻找最好的算法,检查数字是否是素数,即布尔函数:
__PRE__
我想知道实现此功能的最佳算法.当然,我可以查询一个数据结构.我定义了最好的算法,它是生成数据结构的算法,该数据结构具有最低的内存消耗范围(1,N),其中N是常量.
Ale*_*dru 206
一般素数测试的最快算法是AKS.维基百科的文章描述了它的长度和原始论文的链接.
如果你想找到大数字,请查看具有特殊形式的素数,如梅森素数.
我通常实现的算法(易于理解和编码)如下(在Python中):
def isprime(n):
"""Returns True if n is prime."""
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
它是经典O(sqrt(N))算法的变体.它使用的是素数(除了2和3)是形式的,6k - 1或者6k + 1只看这种形式的除数.
有时,如果我真的想要速度并且范围有限,我会根据费马的小定理实现伪素数检验.如果我真的想要更快的速度(即完全避免使用O(sqrt(N))算法),我会预先计算误报(参见Carmichael数字)并进行二分搜索.这是迄今为止我实施过的最快的测试,唯一的缺点是范围有限.
- 两个问题:你能更好地解释变量`i`和`w`是什么,以及形式`6k-1`和`6k + 1`是什么意思？感谢您的见解和代码示例(我正在努力理解) (7认同)
- 计算一次`n`的`sqrt`并将`i`与它进行比较,而不是在循环的每个循环中计算`i*i`,这不是更好吗？ (6认同)
- @Freedom_Ben在这里,http://www.quora.com/Is-every-prime-number-other-than-2-and-3-of-the-form-6k±1 (5认同)
- 实际上 AKS 不是最快的实现。 (3认同)
- @Dschoni ...但你不能在这里的评论字段中适应最快的实现与我们分享？ (3认同)
- 严格来说,Carmicheals是不够的.您的伪素数测试也必须不会无意中错过反驳FLT所需的正确基础.强伪伪算法的优势在于没有相关的"Carmicheals",但除非你检查了至少四分之一的范围,否则你仍然无法确定.如果你没有范围限制,那么在我看来,使用SPP +像pollard rho这样的东西来分类绝对大多数的第一遍数字,然后再使用更重的东西是正确的方法. (2认同)
- 它失败了1号:( (2认同)
pax*_*blo 26
在我看来,最好的方法是使用以前的方法.
N互联网上有第一批素数的列表,N至少有五千万.下载文件并使用它们,它可能比你想出的任何其他方法快得多.
如果你想制作自己的素数的实际算法,维基百科对素数各种各样的好东西在这里,包括链接到做它的各种方法和主要测试在这里,无论是基于概率的和快速确定性方法.
应该齐心协力找到最初的十亿(甚至更多)素数并将它们发布到网上的某个地方,以便人们可以一遍又一遍地停止做同样的工作...... :-)
- @hamedbh:很有意思.你试过下载这些文件吗？它们似乎不存在. (2认同)
- @CogitoErgoCogitoSum,同意所有素数的列表将永远过时,因为我已经看到数学证明它们的数量是无限的.但是,第一个`x`素数列表一旦建成就不太可能不完整:-) (2认同)
小智 9
bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
this is just c++ implementation of above AKS algorithm
https://en.wikipedia.org/wiki/AKS_primality_test
- 它是我遇到过的最有效的确定性算法之一，是的，但它不是 AKS 的实现。AKS 系统比概述的算法要新得多。可以说它更有效，但由于潜在的天文大阶乘/二项式系数，imo 实现起来有些困难。 (2认同)
我比较了最流行的建议的效率，以确定数字是否为质数。我用python 3.6的ubuntu 17.10; 我测试了高达100.000的数字（您可以使用下面的代码测试更大的数字）。
第一个图比较了这些函数（在我的答案中作了进一步解释），表明当增加数字时，最后一个函数的增长速度不如第一个函数快。
在第二个图表中，我们可以看到在质数的情况下时间稳定增长，但是非质数的时间却没有那么快地增长（因为大多数可以在早期被消除）。
这是我使用的功能：
-
Run Code Online (Sandbox Code Playgroud)def is_prime_1(n): return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1)) 这个答案使用了某种while循环：
Run Code Online (Sandbox Code Playgroud)def is_prime_2(n): if n <= 1: return False if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True这个答案包括一个带有
for循环的版本：
Run Code Online (Sandbox Code Playgroud)def is_prime_3(n): if n <= 1: return False if n % 2 == 0 and n > 2: return False for i in range(3, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True然后，我将其他答案中的一些想法融合到一个新的想法中：
Run Code Online (Sandbox Code Playgroud)def is_prime_4(n): if n <= 1: # negative numbers, 0 or 1 return False if n <= 3: # 2 and 3 return True if n % 2 == 0 or n % 3 == 0: return False for i in range(5, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True
这是我用来比较变体的脚本：
import math
import pandas as pd
import seaborn as sns
import time
from matplotlib import pyplot as plt
def is_prime_1(n):
...
def is_prime_2(n):
...
def is_prime_3(n):
...
def is_prime_4(n):
...
default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4)
def assert_equal_results(func_list=default_func_list, n):
for i in range(-2, n):
r_list = [f(i) for f in func_list]
if not all(r == r_list[0] for r in r_list):
print(i, r_list)
raise ValueError
print('all functions return the same results for integers up to {}'.format(n))
def compare_functions(func_list=default_func_list, n):
result_list = []
n_measurements = 3
for f in func_list:
for i in range(1, n + 1):
ret_list = []
t_sum = 0
for _ in range(n_measurements):
t_start = time.perf_counter()
is_prime = f(i)
t_end = time.perf_counter()
ret_list.append(is_prime)
t_sum += (t_end - t_start)
is_prime = ret_list[0]
assert all(ret == is_prime for ret in ret_list)
result_list.append((f.__name__, i, is_prime, t_sum / n_measurements))
df = pd.DataFrame(
data=result_list,
columns=['f', 'number', 'is_prime', 't_seconds'])
df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2))
print('df.shape:', df.shape)
print()
print('', '-' * 41)
print('| {:11s} | {:11s} | {:11s} |'.format(
'is_prime', 'count', 'percent'))
df_sub1 = df[df['f'] == 'is_prime_1']
print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
'all', df_sub1.shape[0], 100))
for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems():
print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
str(is_prime), count, count * 100 / df_sub1.shape[0]))
print('', '-' * 41)
print()
print('', '-' * 69)
print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format(
'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)'))
for f, df_sub1 in df.groupby(['f', ]):
col = df_sub1['t_micro_seconds']
print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13))
print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
f, 'all', col.min(), col.mean(), col.max()))
for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]):
col = df_sub2['t_micro_seconds']
print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
f, str(is_prime), col.min(), col.mean(), col.max()))
print('', '-' * 69)
return df
运行该函数compare_functions(n=10**5)（最多100.000），我得到以下输出：
df.shape: (400000, 5)
-----------------------------------------
| is_prime | count | percent |
| all | 100,000 | 100.0 % |
| False | 90,408 | 90.4 % |
| True | 9,592 | 9.6 % |
-----------------------------------------
---------------------------------------------------------------------
| f | is_prime | t min (us) | t mean (us) | t max (us) |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1 | all | 0.57 | 2.50 | 154.35 |
| is_prime_1 | False | 0.57 | 1.52 | 154.35 |
| is_prime_1 | True | 0.89 | 11.66 | 55.54 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2 | all | 0.24 | 1.14 | 304.82 |
| is_prime_2 | False | 0.24 | 0.56 | 304.82 |
| is_prime_2 | True | 0.25 | 6.67 | 48.49 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3 | all | 0.20 | 0.95 | 50.99 |
| is_prime_3 | False | 0.20 | 0.60 | 40.62 |
| is_prime_3 | True | 0.58 | 4.22 | 50.99 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4 | all | 0.20 | 0.89 | 20.09 |
| is_prime_4 | False | 0.21 | 0.53 | 14.63 |
| is_prime_4 | True | 0.20 | 4.27 | 20.09 |
---------------------------------------------------------------------
然后，运行该函数compare_functions(n=10**6)（最大为1.000.000），得到以下输出：
df.shape: (4000000, 5)
-----------------------------------------
| is_prime | count | percent |
| all | 1,000,000 | 100.0 % |
| False | 921,502 | 92.2 % |
| True | 78,498 | 7.8 % |
-----------------------------------------
---------------------------------------------------------------------
| f | is_prime | t min (us) | t mean (us) | t max (us) |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1 | all | 0.51 | 5.39 | 1414.87 |
| is_prime_1 | False | 0.51 | 2.19 | 413.42 |
| is_prime_1 | True | 0.87 | 42.98 | 1414.87 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2 | all | 0.24 | 2.65 | 612.69 |
| is_prime_2 | False | 0.24 | 0.89 | 322.81 |
| is_prime_2 | True | 0.24 | 23.27 | 612.69 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3 | all | 0.20 | 1.93 | 67.40 |
| is_prime_3 | False | 0.20 | 0.82 | 61.39 |
| is_prime_3 | True | 0.59 | 14.97 | 67.40 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4 | all | 0.18 | 1.88 | 332.13 |
| is_prime_4 | False | 0.20 | 0.74 | 311.94 |
| is_prime_4 | True | 0.18 | 15.23 | 332.13 |
---------------------------------------------------------------------
我使用以下脚本来绘制结果：
def plot_1(func_list=default_func_list, n):
df_orig = compare_functions(func_list=func_list, n=n)
df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20]
sns.lmplot(
data=df_filtered, x='number', y='t_micro_seconds',
col='f',
# row='is_prime',
markers='.',
ci=None)
plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3))
plt.show()
根据维基百科的说法,Eratosthenes的Sieve具有复杂性O(n * (log n) * (log log n))并且需要O(n)记忆 - 所以如果你没有测试特别大的数字,那么这是一个非常好的起点.
小智 6
在Python 3中：
def is_prime(a):
if a < 2:
return False
elif a!=2 and a % 2 == 0:
return False
else:
return all (a % i for i in range(3, int(a**0.5)+1))
说明： 质数是只能被其自身和1整除的数字。例如：2,3,5,7 ...
1）如果a <2：如果“ a”小于2，则不是质数。
2）elif a！= 2和％2 == 0：如果“ a”可被2整除，则其绝对不是质数。但是，如果a = 2，我们不想对其进行评估，因为它是质数。因此条件a！= 2
3）返回all（range（3，int（a 0.5）+1）中i的a％i）：**首先看一下all（）命令在python中的作用。从3开始，我们将“ a”除以其平方根（a ** 0.5）。如果“ a”是可分割的，则输出将为False。为什么是平方根？假设a = 16。16的平方根=4。我们不需要评估直到15。我们只需要检查直到4就可以说它不是素数。
额外： 一个循环，用于查找范围内的所有素数。
for i in range(1,100):
if is_prime(i):
print("{} is a prime number".format(i))
- 这与 [Oleksandr Shmyheliuk 的回答](/sf/answers/3134991681/) 有何不同？（两者都错过了 `range()` 中的“第 2 步”……） (2认同)
可以使用sympy。
import sympy
sympy.ntheory.primetest.isprime(33393939393929292929292911111111)
True
来自sympy文档。第一步是寻找微不足道的因素，如果发现这些因素，便可以迅速获得回报。接下来，如果筛子足够大，请在筛子上使用二等分搜索。对于少量样本，使用确定范围内没有反例的碱基执行一组确定性Miller-Rabin测试。最后，如果该数字大于2 ^ 64，则执行强的BPSW测试。尽管这是一个可能的主要测试，并且我们相信存在反例，但尚无已知的反例
- @老人。来自sympy文档。第一步是寻找微不足道的因素，如果发现这些因素，便可以迅速获得回报。接下来，如果筛子足够大，请在筛子上使用二等分搜索。对于少量样本，使用确定范围内没有反例的碱基执行一组确定性Miller-Rabin测试。最后，如果该数字大于2 ^ 64，则执行强的BPSW测试。尽管这是一个可能的主要测试，并且我们相信存在反例，但尚无已知的反例。 (2认同)