如何创建最紧凑的映射 n → isprime(n) 直到极限 N？
- 2025-01-06 08:32:00
- admin 原创
- 102
问题描述：
当然，因为bool isprime(number)会有一个我可以查询的数据结构。
我定义了最佳算法，即在范围 (1, N] 内生成内存消耗最低的数据结构的算法，其中 N 是常数。
这只是我正在寻找的一个例子：我可以用一位表示每个奇数，例如对于给定的数字范围 (1, 10]，从 3 开始：1110
下面的字典可以压缩得更多，对吧？我可以通过一些工作消除 5 的倍数，但以 1、3、7 或 9 结尾的数字必须存在于位数组中。
我该如何解决这个问题？
解决方案 1：
一般素数测试的最快算法是AKS。 Wikipedia 文章对其进行了详细描述，并提供了原始论文的链接。
如果想要找到大数字，请查看具有特殊形式的素数，例如梅森素数。
我通常实现的算法（易于理解和编码）如下（使用 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
它是经典算法的一个变体。它利用素数（2 和 3 除外）的形式为或 的O(sqrt(N))事实，并且只考虑这种形式的除数。6k - 1`6k + 1`
有时，如果我真的想要速度并且范围有限，我会根据费马小定理实现伪素数测试。如果我真的想要更快的速度（即完全避免 O(sqrt(N)) 算法），我会预先计算误报（参见卡迈克尔数）并进行二分搜索。这是迄今为止我实现过的最快的测试，唯一的缺点是范围有限。
解决方案 2：
一个非常简单且简洁的强力解决方案来检查数字 N 是否为质数：只需检查是否有从 2 到 N 的平方根的 N 的除数（如果感兴趣，请在此处查看原因）。
以下代码与 Python 2 和 Python 3 兼容：
from math import sqrt
from itertools import count, islice
def is_prime(n):
return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n) - 1)))
这是一个更简单的 Python 3 实现：
def is_prime(n):
return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))
为了清楚起见，以下是上述内容的扩展版本：
from math import sqrt
from itertools import count, islice
def is_prime(n):
if n < 2:
return False
for divisor in islice(count(2), int(sqrt(n) - 1)):
if n % divisor == 0:
return False
return True
def is_prime(n):
if n < 2:
return False
for divisor in range(2, int(n ** 0.5) + 1):
if n % divisor == 0:
return False
return True
这并不意味着它是最快或最优化的素数检查算法，它只实现了简单和简洁的目标，这也减少了实现错误。它的时间复杂度为O(sqrt(n))。
如果您正在寻找更快的算法来检查一个数字是否为素数，您可能会对以下内容感兴趣：
寻找素数和证明素数：对最著名的素数测试及其历史的简要概述和解释。
概率素数测试（维基百科）：这些可以很容易地合并到上面的代码中，如果它们没有通过，就可以跳过蛮力破解，例如，对这个问题的重复有一个很好的答案。
快速确定性素数测试（维基百科）
此问答以最快的方式列出 N 以下的所有素数以及
pyprimesieve库。
实施说明
您可能已经注意到，在 Python 2 兼容实现中，我使用的是itertools.count()与 的组合，itertools.islice()而不是简单的range()或xrange()（旧的 Python 2生成器范围，在 Python 3 中是默认值）。这是因为在 CPython 2 中，xrange(N)对于某个 N，例如 N > 2 63 - 1（或 N > 2 31 - 1，取决于实现）会引发OverflowError。这是一个不幸的 CPython 实现细节。
我们可以使用itertools来解决这个问题。由于我们使用 从 开始计数到2无穷大，因此我们将在步骤之后itertools.count(2)达到，并且我们可以使用 来限制生成器。sqrt(n)`sqrt(n) - 1`itertools.islice()
解决方案 3：
有很多有效的方法来测试素数（这不是其中之一），但是你编写的循环可以用 Python 简洁地重写：
def is_prime(a):
return all(a % i for i in xrange(2, a))
也就是说，如果 2 和 a 之间（不包括 2 和 a）的所有数字除以 a 时余数都是非零，则 a 为素数。
解决方案 4：
如果您只有几个查询，这是判断数字是否为素数的最有效方法。如果您要查询很多数字是否为素数，请尝试埃拉托斯特尼筛法。
import math
def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n % divisor == 0:
return False
return True
解决方案 5：
如果a是素数，那么while x:代码中的将永远运行，因为x将保持True。
那么它为什么while在那里呢？
我认为您想在找到一个因子时结束 for 循环，但不知道如何做，所以您添加了 while，因为它有一个条件。因此，您可以这样做：
def is_prime(a):
x = True
for i in range(2, a):
if a%i == 0:
x = False
break # ends the for loop
# no else block because it does nothing ...
if x:
print "prime"
else:
print "not prime"
解决方案 6：
我比较了最流行的确定数字是否为质数的建议的效率。我使用python 3.6了ubuntu 17.10；我测试了高达 100.000 的数字（您可以使用下面的代码测试更大的数字）。
第一个图比较了这些函数（在我的回答中进一步解释），表明在增加数字时，最后一个函数的增长速度不如第一个函数快。
在第二个图中，我们可以看到，对于素数来说，时间稳步增长，但非素数的时间增长速度并不那么快（因为大多数非素数可以在早期被消除）。
以下是我使用的功能：
这个答案和这个答案建议使用以下构造
all()：
def is_prime_1(n):
return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1))
这个答案使用了某种 while 循环：
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循环的版本：
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
我将其他答案中的一些想法混合成一个新的想法：
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()
解决方案 7：
可以使用 sympy。
import sympy
sympy.ntheory.primetest.isprime(33393939393929292929292911111111)
True
来自 sympy 文档。第一步是寻找琐碎因子，如果找到，可以快速返回。接下来，如果筛子足够大，则在筛子上使用二分搜索。对于较小的数字，使用已知在其范围内没有反例的基数执行一组确定性 Miller-Rabin 测试。最后，如果数字大于 2^64，则执行强 BPSW 测试。虽然这是一个可能的素数测试，并且我们相信存在反例，但没有已知的反例
解决方案 8：
根据维基百科，埃拉托斯特尼筛选法具有复杂性O(n * (log n) * (log log n))并且需要O(n)内存- 因此如果您不测试特别大的数字，这是一个很好的起点。
解决方案 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;
}
这只是上述的 C++ 实现
解决方案 10：
对于大数，您不能简单地天真地检查候选数字 N 是否不能被小于 sqrt(N) 的任何数字整除。有更多可扩展的测试可用，例如Miller-Rabin 素数测试。下面是 Python 中的实现：
def is_prime(x):
"""Fast implementation fo Miller-Rabin primality test, guaranteed to be correct."""
import math
def get_sd(x):
"""Returns (s: int, d: int) for which x = d*2^s """
if not x: return 0, 0
s = 0
while 1:
if x % 2 == 0:
x /= 2
s += 1
else:
return s, x
if x <= 2:
return x == 2
# x - 1 = d*2^s
s, d = get_sd(x - 1)
if not s:
return False # divisible by 2!
log2x = int(math.log(x) / math.log(2)) + 1
# As long as Riemann hypothesis holds true, it is impossible
# that all the numbers below this threshold are strong liars.
# Hence the number is guaranteed to be a prime if no contradiction is found.
threshold = min(x, 2*log2x*log2x+1)
for a in range(2, threshold):
# From Fermat's little theorem if x is a prime then a^(x-1) % x == 1
# Hence the below must hold true if x is indeed a prime:
if pow(a, d, x) != 1:
for r in range(0, s):
if -pow(a, d*2**r, x) % x == 1:
break
else:
# Contradicts Fermat's little theorem, hence not a prime.
return False
# No contradiction found, hence x must be a prime.
return True
你可以使用它来查找巨大的素数：
x = 10000000000000000000000000000000000000000000000000000000000000000000000000000
for e in range(1000):
if is_prime(x + e):
print('%d is a prime!' % (x + e))
break
# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!
如果您正在测试随机整数，那么在调用 Miller-Rabin 之前，您可能希望先测试候选数字是否能被小于 1000 的任何素数整除。这将帮助您过滤掉明显的非素数，例如 10444344345。
解决方案 11：
Python 3：
def is_prime(a):
return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))
解决方案 12：
参加聚会已经太晚了，但希望这能有所帮助。如果你正在寻找大素数，那么这很有用：
要测试较大的奇数，您需要使用费马检验和/或米勒-拉宾检验。
这些测试使用了非常昂贵的模幂运算，对于n位幂运算，至少需要n大整数乘法和n大整数除法。这意味着模幂运算的复杂度为 O(n³)。
因此，在使用大炮之前，您需要进行相当多的试除法。但不要天真地这样做，有一种方法可以快速完成它们。首先，将尽可能多的素数乘以与大整数使用的字数相同的数。如果使用 32 位字，则乘以 357111317192329=3234846615，然后使用欧几里得算法计算与您测试的数字的最大公约数。第一步之后，数字减少到字大小以下，并继续算法而不执行完整的大整数除法。如果 GCD != 1，则意味着您相乘的素数之一可以整除该数字，因此您可以证明它不是素数。然后继续 3137414347 = 95041567，依此类推。
一旦您通过这种方式测试了几百（或几千）个素数，您就可以进行 40 轮米勒-拉宾测试来确认该数字是否为素数，40 轮之后，您就可以确定该数字是素数，只有 2^-80 的机会它不是素数（更可能是您的硬件出现故障……）。
解决方案 13：
我有一个素数函数，其工作直到 (2^61)-1 这里：
from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))
解释：
该all()函数可以重新定义为：
def all(variables):
for element in variables:
if not element: return False
return True
该all()函数仅遍历一系列布尔值/数字，False如果看到 0 或 则返回False。
该sqrt()函数只是计算数字的平方根。
例如：
>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10
该num % x部分返回num / x 的余数。
最后，range(2, int(sqrt(num)))意味着它将创建一个从2 开始到int(sqrt(num)+1)
有关范围的更多信息，请查看此网站！
该num > 1部分只是检查变量是否num大于 1，因为 1 和 0 不被视为质数。
希望这对你有帮助:)
解决方案 14：
在 Python 中：
def is_prime(n):
return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))
从数学形式主义到 Python 的更直接转换将使用all(n % p != 0... )，但这需要严格评估 p 的所有值。如果发现 True 值，则not any版本可以提前终止。
解决方案 15：
素数 javascript 的最佳算法
function isPrime(num) {
if (num <= 1) return false;
else if (num <= 3) return true;
else if (num % 2 == 0 || num % 3 == 0) return false;
var i = 5;
while (i * i <= num) {
if (num % i == 0 || num % (i + 2) == 0) return false;
i += 6;
}
return true
}
解决方案 16：
质数是只能被 1 和它本身整除的任何数字。所有其他数字都称为合数。
寻找素数的最简单方法是检查输入数字是否是合数：
function isPrime(number) {
// Check if a number is composite
for (let i = 2; i < number; i++) {
if (number % i === 0) {
return false;
}
}
// Return true for prime numbers
return true;
}
程序必须用 的值number除以从 1 到 的所有整数。如果这个数字不仅可以被 1 和它本身整除，那么它就是合数。
该变量的初始值i必须是 2，因为质数和合数都可以被 1 整除。
for (let i = 2; i < number; i++)
则i小于，number原因相同。素数和合数都可以被自身整除。因此，没有理由检查它。
然后我们使用余数运算符检查该变量是否可以被整除。
if (number % i === 0) {
return false;
}
如果余数为零，则意味着number可以被整除，因此是合数并返回 false。
如果输入的数字不符合条件，则表示它是一个质数，函数返回 true。
解决方案 17：
最小内存？这不是最小的，但这是朝着正确方向迈出的一步。
class PrimeDictionary {
BitArray bits;
public PrimeDictionary(int n) {
bits = new BitArray(n + 1);
for (int i = 0; 2 * i + 3 <= n; i++) {
bits.Set(i, CheckPrimality(2 * i + 3));
}
}
public PrimeDictionary(IEnumerable<int> primes) {
bits = new BitArray(primes.Max());
foreach(var prime in primes.Where(p => p != 2)) {
bits.Set((prime - 3) / 2, true);
}
}
public bool IsPrime(int k) {
if (k == 2) {
return true;
}
if (k % 2 == 0) {
return false;
}
return bits[(k - 3) / 2];
}
}
当然，你必须指定 的定义CheckPrimality。
解决方案 18：
判断某个范围内的数字是否为质数。
#!usr/bin/python3
def prime_check(*args):
for arg in args:
if arg > 1: # prime numbers are greater than 1
for i in range(2,arg): # check for factors
if(arg % i) == 0:
print(arg,"is not Prime")
print(i,"times",arg//i,"is",arg)
break
else:
print(arg,"is Prime")
# if input number is less than
# or equal to 1, it is not prime
else:
print(arg,"is not Prime")
return
# Calling Now
prime_check(*list(range(101))) # This will check all the numbers in range 0 to 100
prime_check(#anynumber) # Put any number while calling it will check.
解决方案 19：
myInp=int(input("Enter a number: "))
if myInp==1:
print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
for i in range(2,myInp//2+1):
if myInp%i==0:
print("The Number {} is not a prime no".format(myInp))
print("Because",i,"times",myInp//i,"is",myInp)
break
else:
print("The Number {} is a prime no".format(myInp))
else:
print("Alas the no {} is a not a prime no".format(myInp))
解决方案 20：
public static boolean isPrime(int number) {
if(number < 2)
return false;
else if(number == 2 || number == 3)
return true;
else {
for(int i=2;i<=number/2;i++)
if(number%i == 0)
return false;
else if(i==number/2)
return true;
}
return false;
}
解决方案 21：
之前的大部分答案都是正确的，但这里还有一种方法可以测试一个数字是否是质数。作为复习，质数是大于 1 的整数，其唯一因数是 1 和它本身。（来源）
解决方案：
通常，您可以建立一个循环并开始测试您的数字，看看它是否能被 1、2、3 整除……直到您要测试的数字……等等，但为了减少检查时间，您可以将您的数字除以该数字值的一半，因为数字不可能被其值一半以上的任何数字精确整除。例如，如果您想看看 100 是否是质数，您可以循环遍历到 50。
实际代码：
def find_prime(number):
if(number ==1):
return False
# we are dividiing and rounding and then adding the remainder to increment !
# to cover not fully divisible value to go up forexample 23 becomes 11
stop=number//2+number%2
#loop through up to the half of the values
for item in range(2,stop):
if number%item==0:
return False
print(number)
return True
if(find_prime(3)):
print("it's a prime number !!")
else:
print("it's not a prime")
解决方案 22：
我们可以使用 Java 流在 O(sqrt(n)) 中实现这一点；考虑到 noneMatch 是一种短路方法，当发现不需要确定结果时会停止操作：
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");
解决方案 23：
借助 Java-8 流和 lambda，只需几行就可以实现如下功能：
public static boolean isPrime(int candidate){
int candidateRoot = (int) Math.sqrt( (double) candidate);
return IntStream.range(2,candidateRoot)
.boxed().noneMatch(x -> candidate % x == 0);
}
性能应该接近O(sqrt(N))。也许有人觉得它有用。
解决方案 24：
### is_prime(number) =
### if number % p1 !=0 for all p1(prime numbers) < (sqrt(number) + 1),
### filter numbers that are not prime from divisors
import math
def check_prime(N, prime_numbers_found = [2]):
if N == 2:
return True
if int(math.sqrt(N)) + 1 > prime_numbers_found[-1]:
divisor_range = prime_numbers_found + list(range(prime_numbers_found[-1] + 1, int(math.sqrt(N)) + 1+ 1))
else:
divisor_range = prime_numbers_found
#print(divisor_range, N)
for number in divisor_range:
if number not in prime_numbers_found:
if check_prime(number, prime_numbers_found):
prime_numbers_found.append(number)
if N % number == 0:
return False
else:
if N % number == 0:
return False
return True
解决方案 25：
bool isPrime(int n) {
if(n <= 3)
return (n > 1)==0? false: true;
else if(n%2 == 0 || n%3 == 0)
return false;
int i = 5;
while(i * i <= n){
if(n%i == 0 || (n%(i+2) == 0))
return false;
i = i + 6;
}
return true;
}
对于任何数字，检查数字是否为素数的最小迭代次数可以是从 2 到数字的平方根。为了进一步减少迭代次数，我们可以检查数字是否能被 2 或 3 整除，因为可以通过检查数字是否能被 2 或 3 整除来消除最大数字。此外，任何大于 3 的素数都可以表示为 6k+1 或 6k-1。因此迭代可以从 6k+1 到数字的平方根。
解决方案 26：
让我向您推荐 64 位整数的完美解决方案。抱歉使用 C#。您还没有在第一篇帖子中将其指定为 python。我希望您能找到一个简单的 modPow 函数并轻松分析它。
public static bool IsPrime(ulong number)
{
return number == 2
? true
: (BigInterger.ModPow(2, number, number) == 2
? ((number & 1) != 0 && BinarySearchInA001567(number) == false)
: false)
}
public static bool BinarySearchInA001567(ulong number)
{
// Is number in list?
// todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
// Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}
解决方案 27：
与之前提到的算法类似的想法
public static boolean isPrime(int n) {
if(n == 2 || n == 3) return true;
if((n & 1 ) == 0 || n % 3 == 0) return false;
int limit = (int)Math.sqrt(n) + 1;
for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
if(n % i == 0) return false;
numChecks++;
}
return true;
}
解决方案 28：
from math import isqrt
def is_prime(n: int) -> bool:
if n <= 3:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False
limit = isqrt(n)
for i in range(5, limit+1, 6):
if n % i == 0 or n % (i+2) == 0:
return False
return True
试分法。
解决方案 29：
最佳解决方案
Time complexity: O(sqrt(n))我不确定我是否理解此上下文中的和的概念Space complexity: O(1)，但该函数prime(n)可能是用于fastest way (least iterations)
计算数字是否为任意大小的质数。
https://github.com/ganeshkbhat/fastprimenumbers
截至 2022 年 3 月 11 日，这可能是互联网上最好的解决方案。欢迎反馈和使用。
相同的代码可以应用于任何语言，如 C、C++、Go Lang、Java、.NET、Python、Rust 等，具有相同的逻辑，并且具有性能优势。它非常快。我以前从未见过这种实现，而且是本土实现的。
如果您关注速度和性能，"""BEST"""我可以给出以下有希望的解决方案：
对于 n == 100000，最大迭代次数为 16666，而不是传统方法的 100000
代码也可以在这里找到：https://github.com/ganeshkbhat/fastprimecalculations
如果您将它用于您的项目，请花 2 分钟时间通过发送电子邮件或以主题为 记录 Github 问题[User]或star我的 Github 项目来告知我。但请在此处告诉我https://github.com/ganeshkbhat/fastprimecalculations。我很想知道代码逻辑的粉丝和用户
def prime(n):
if ((n == 2 or n == 3 or n == 5 or n == 7)):
return True
if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
return False
if ( type((n - 1) / 6) == int or type((n + 1) / 6) == int):
for i in range(1, n):
factorsix = (i * 6)
five = n / (5 + factorsix)
seven = n / (7 + factorsix)
if ( ((five > 1) and type(five) == int) or ((seven > 1) and type(five) == int) ):
return False;
if (factorsix > n):
break;
return True
return False
下面对所有计算方式进行分析：
检查素数的常规方法：
def isPrimeConventionalWay(n):
count = 0
if (n <= 1):
return False;
# Check from 2 to n-1
# Max iterations 99998 for n == 100000
for i in range(2,n):
# Counting Iterations
count += 1
if (n % i == 0):
print("count: Prime Conventional way", count)
return False;
print("count: Prime Conventional way", count)
return True;
检查素数的 SQUAREROOT 方法：
def isPrimeSquarerootWay(num):
count = 0
# if not is_number num return False
if (num < 2):
print("count: Prime Squareroot way", count)
return False
s = math.sqrt(num)
for i in range(2, num):
# Counting Iterations
count += 1
if (num % i == 0):
print("count: Prime Squareroot way", count)
return False
print("count: Prime Squareroot way", count)
return True
其他方式：
def isprimeAKSWay(n):
"""Returns True if n is prime."""
count = 0
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:
count += 1
if n % i == 0:
print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
return False
i += w
w = 6 - w
print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
return True
检查素数的建议方法：
def prime(n):
count = 0
if ((n == 2 or n == 3 or n == 5 or n == 7)):
print("count: Prime Unconventional way", count)
return True
if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
print("count: Prime Unconventional way", count)
return False
if (((n - 1) / 6).is_integer()) or (((n + 1) / 6).is_integer()):
for i in range(1, n):
# Counting Iterations
count += 1
five = 5 + (i * 6)
seven = 7 + (i * 6)
if ((((n / five) > 1) and (n / five).is_integer()) or (((n / seven) > 1) and ((n / seven).is_integer()))):
print("count: Prime Unconventional way", count)
return False;
if ((i * 6) > n):
# Max iterations 16666 for n == 100000 instead of 100000
break;
print("count: Prime Unconventional way", count)
return True
print("count: Prime Unconventional way", count)
return False
测试与检查素数的传统方法进行比较。
def test_primecalculations():
count = 0
iterations = 100000
arr = []
for i in range(1, iterations):
traditional = isPrimeConventionalWay(i)
newer = prime(i)
if (traditional == newer):
count = count + 1
else:
arr.push([traditional, newer, i])
print("[count, iterations, arr] list: ", count, iterations, arr)
if (count == iterations):
return True
return False
# print("Tests Passed: ", test_primecalculations())
您将看到以下迭代次数计算结果check of prime number: 100007：
print("Is Prime 100007: ", isPrimeConventionalWay(100007))
print("Is Prime 100007: ", isPrimeSquarerootWay(100007))
print("Is Prime 100007: ", prime(100007))
print("Is Prime 100007: ", isprimeAKSWay(100007))
count: Prime Conventional way 96
Is Prime 100007: False
count: Prime Squareroot way 96
Is Prime 100007: False
count: Prime Unconventional way 15
Is Prime 100007: False
count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way 32
Is Prime 100007: False
以下是一些性能测试和结果：
import time
isPrimeConventionalWayArr = []
isPrimeSquarerootWayArr = []
primeArr = []
isprimeAKSWayArr = []
def tests_performance_isPrimeConventionalWayArr():
global isPrimeConventionalWayArr
for i in range(1, 1000000):
start = time.perf_counter_ns()
isPrimeConventionalWay(30000239)
end = time.perf_counter_ns()
isPrimeConventionalWayArr.append(end - start)
tests_performance_isPrimeConventionalWayArr()
def tests_performance_isPrimeSquarerootWayArr():
global isPrimeSquarerootWayArr
for i in range(1, 1000000):
start = time.perf_counter_ns()
isPrimeSquarerootWay(30000239)
end = time.perf_counter_ns()
isPrimeSquarerootWayArr.append(end - start)
tests_performance_isPrimeSquarerootWayArr()
def tests_performance_primeArr():
global primeArr
for i in range(1, 1000000):
start = time.perf_counter_ns()
prime(30000239)
end = time.perf_counter_ns()
primeArr.append(end - start)
tests_performance_primeArr()
def tests_performance_isprimeAKSWayArr():
global isprimeAKSWayArr
for i in range(1, 1000000):
start = time.perf_counter_ns()
isprimeAKSWay(30000239)
end = time.perf_counter_ns()
isprimeAKSWayArr.append(end - start)
tests_performance_isprimeAKSWayArr()
print("isPrimeConventionalWayArr: ", sum(isPrimeConventionalWayArr)/len(isPrimeConventionalWayArr))
print("isPrimeSquarerootWayArr: ", sum(isPrimeSquarerootWayArr)/len(isPrimeSquarerootWayArr))
print("primeArr: ", sum(primeArr)/len(primeArr))
print("isprimeAKSWayArr: ", sum(isprimeAKSWayArr)/len(isprimeAKSWayArr))
采样 100 万次迭代
迭代 1：
isPrimeConventionalWayArr: 1749.97224997225
isPrimeSquarerootWayArr: 1835.6258356258356
primeArr (suggested): 475.2365752365752
isprimeAKSWayArr: 1177.982377982378
迭代 2：
isPrimeConventionalWayArr: 1803.141403141403
isPrimeSquarerootWayArr: 2184.222484222484
primeArr (suggested): 572.6434726434726
isprimeAKSWayArr: 1403.3838033838033
迭代 3：
isPrimeConventionalWayArr: 1876.941976941977
isPrimeSquarerootWayArr: 2190.43299043299
primeArr (suggested): 569.7365697365698
isprimeAKSWayArr: 1449.4147494147494
迭代 4：
isPrimeConventionalWayArr: 1873.2779732779734
isPrimeSquarerootWayArr: 2177.154777154777
primeArr (suggested): 590.4243904243905
isprimeAKSWayArr: 1401.9143019143019
迭代 5：
isPrimeConventionalWayArr: 1891.1986911986912
isPrimeSquarerootWayArr: 2218.093218093218
primeArr (suggested): 571.6938716938716
isprimeAKSWayArr: 1397.6471976471976
迭代 6：
isPrimeConventionalWayArr: 1868.8454688454688
isPrimeSquarerootWayArr: 2168.034368034368
primeArr (suggested): 566.3278663278663
isprimeAKSWayArr: 1393.090193090193
迭代 7：
isPrimeConventionalWayArr: 1879.4764794764794
isPrimeSquarerootWayArr: 2199.030199030199
primeArr (suggested): 574.055874055874
isprimeAKSWayArr: 1397.7587977587978
迭代 8：
isPrimeConventionalWayArr: 1789.2868892868894
isPrimeSquarerootWayArr: 2182.3258823258825
primeArr (suggested): 569.3206693206694
isprimeAKSWayArr: 1407.1486071486072
解决方案 30：
当我必须进行快速验证时，我会根据输入的平方根以下的数字之间的基本除法编写这个简单的代码。
def isprime(n):
if n%2==0:
return n==2
else:
cota = int(n**0.5)+1
for ind in range(3,2,cota):
if n%ind==0:
print(ind)
return False
is_one = n==1
return True != is_one
isprime(22783)
最后
True != n==1就是避免这种情况n=1。
相关推荐
热门文章
项目管理软件有哪些？
热门标签
云禅道AD
