当然，因为bool isprime(number)会有我可以查询的数据结构。
我将最好的算法定义为在 (1, N] 范围内产生具有最低内存消耗的数据结构的算法，其中 N 是一个常数。
只是我正在寻找的一个示例：我可以表示每个奇数例如，对于给定的数字范围 (1, 10]，一位从 3 开始：1110
下面的字典可以多挤一点吧？我可以通过一些工作消除五的倍数，但是以 1、3、7 或 9 结尾的数字必须存在于位数组中。
我该如何解决这个问题？
问问题
279277 次
28 回答
219
The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper.
If you want to find big numbers, look into primes that have special forms like Mersenne primes.
The algorithm I usually implement (easy to understand and code) is as follows (in 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
It's a variant of the classic O(sqrt(N)) algorithm. It uses the fact that a prime (except 2 and 3) is of form 6k - 1 or 6k + 1 and looks only at divisors of this form.
Sometimes, If I really want speed and the range is limited, I implement a pseudo-prime test based on Fermat's little theorem. If I really want more speed (i.e. avoid O(sqrt(N)) algorithm altogether), I precompute the false positives (see Carmichael numbers) and do a binary search. This is by far the fastest test I've ever implemented, the only drawback is that the range is limited.
于 2009-11-26T03:55:00.023 回答
138
检查数字 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)).
如果您正在寻找更快的算法来检查数字是否为素数，您可能对以下内容感兴趣：
- 寻找素数和证明素数：对最著名的素数测试及其历史的简要概述和解释。
- Probabilistic primality tests (Wikipedia)：这些可以很容易地合并到上面的代码中，如果它们没有通过，可以很容易地跳过蛮力，例如，这个问题的副本有这个很好的答案。
- 快速确定性初步测试（维基百科）
- 这是列出 N 以下所有素数以及
pyprimesieve库的最快方式。
实施说明
您可能已经注意到，在与 Python 2 兼容的实现中，我使用itertools.count()了 withitertools.islice()而不是简单的range()or xrange()（旧的 Python 2生成器范围，在 Python 3 中是默认的）。这是因为在 CPython 2xrange(N)中，对于某些 N 使得 N > 2 63 ‒ 1（或 N > 2 31 ‒ 1，取决于实现）会引发OverflowError. 这是一个不幸的 CPython 实现细节。
我们可以用它itertools来克服这个问题。由于我们2使用 来计数到无穷大itertools.count(2)，我们将sqrt(n)在sqrt(n) - 1步骤之后到达，并且我们可以使用 来限制生成器itertools.islice()。
于 2015-01-14T15:39:53.797 回答
80
有许多有效的方法来测试素数（这不是其中之一），但是您编写的循环可以用 Python 简洁地重写：
def is_prime(a):
return all(a % i for i in xrange(2, a))
也就是说，如果 2 和 a（不包括）之间的所有数字在划分为 a 时给出非零余数，则 a 是素数。
于 2010-11-07T13:20:25.423 回答
42
如果您只有几个查询，这是查看数字是否为素数的最有效方法。如果您询问很多数字是否为素数，请尝试使用埃拉托色尼筛法。
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
于 2013-06-29T07:43:59.277 回答
17
如果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"
于 2010-11-06T17:19:47.553 回答
8
可以使用 sympy。
import sympy
sympy.ntheory.primetest.isprime(33393939393929292929292911111111)
True
来自同情文档。第一步是寻找微不足道的因素，如果找到，可以快速返回。接下来，如果筛子足够大，请在筛子上使用二分搜索。对于小数，使用已知在其范围内没有反例的碱基执行一组确定性 Miller-Rabin 检验。最后，如果数字大于 2^64，则执行强 BPSW 测试。虽然这是一个可能的主要测试并且我们相信存在反例，但没有已知的反例
于 2018-08-26T10:30:31.600 回答
8
我比较了最流行的建议的效率，以确定一个数字是否是素数。我用过python 3.6；ubuntu 17.10我测试了高达 100.000 的数字（您可以使用下面的代码测试更大的数字）。
第一个图比较了函数（在我的答案中进一步解释），表明当增加数字时，最后一个函数的增长速度不如第一个函数快。
在第二个图中，我们可以看到，在素数的情况下，时间稳定增长，但非素数的时间增长不那么快（因为它们中的大多数可以在早期被消除）。
以下是我使用的功能：
-
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()
于 2018-11-23T17:57:32.597 回答
7
根据维基百科的说法，埃拉托色尼筛法很复杂O(n * (log n) * (log log n))并且需要O(n)内存——所以如果你不测试特别大的数字，这是一个很好的起点。
于 2009-11-26T03:36:25.020 回答
7
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;
}
这只是上述AKS 算法的 c++ 实现
于 2017-05-17T05:31:53.953 回答
3
对于大数，您不能简单地检查候选数 N 是否可被任何小于 sqrt(N) 的数整除。有更多可扩展的测试可用，例如Miller-Rabin primality test。下面你在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。
于 2019-02-09T16:33:33.623 回答
2
蟒蛇 3：
def is_prime(a):
return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))
于 2017-06-27T16:37:37.393 回答
2
参加聚会为时已晚，但希望这会有所帮助。如果您正在寻找大素数，这很重要：
要测试大奇数，您需要使用 Fermat 测试和/或 Miller-Rabin 测试。
这些测试使用非常昂贵的模幂运算，对于n位求幂，您至少需要n大整数乘法和n大整数除法。这意味着模幂运算的复杂度为 O(n³)。
所以在使用大炮之前，你需要做不少试炼师。但不要天真地去做，有一种方法可以快速完成。首先将尽可能多的素数乘以适合您用于大整数的单词。如果您使用 32 位字，请乘以 3*5*7*11*13*17*19*23*29=3234846615 并使用欧几里得算法测试的数字计算最大公约数。在第一步之后，数字减少到字大小以下并继续算法而不执行完整的大整数除法。如果 GCD != 1，则意味着您相乘的素数之一除以该数字，因此您有证据证明它不是素数。然后继续 31*37*41*43*47 = 95041567，以此类推。
一旦您以这种方式测试了数百个（或数千个）素数，您可以进行 40 轮 Miller-Rabin 测试以确认该数是素数，40 轮后您可以确定该数是素数，只有 2^-80 的机会它是不是（更有可能是您的硬件故障......）。
于 2018-04-27T09:16:00.340 回答
1
让我向您推荐 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
}
于 2020-07-19T01:08:14.623 回答
1
Primes数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
}
于 2018-06-23T05:01:15.170 回答
1
在 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版本可以提前终止。
于 2018-05-22T14:54:48.363 回答
1
我有一个素数函数，它可以工作到 (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 不被视为素数。
我希望这有帮助:)
于 2018-05-11T08:40:17.147 回答
1
素数是任何只能被 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 到其值的所有整数。如果这个数不仅可以被一个和它本身整除，那么它就是一个合数。
变量的初始值i必须是 2，因为素数和合数都可以被 1 整除。
for (let i = 2; i < number; i++)
然后i小于number同理。素数和合数都可以自己整除。因此没有理由检查它。
然后我们使用余数运算符检查变量是否可以被均分。
if (number % i === 0) {
return false;
}
如果余数为零，则意味着number可以被均分，因此是一个合数并返回 false。
如果输入的数字不满足条件，则表示它是质数，函数返回true。
于 2019-07-27T16:51:20.840 回答
0
最小的内存？这不是最小的，而是朝着正确方向迈出的一步。
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.
于 2009-11-26T03:45:57.420 回答
0
以前的大多数答案都是正确的，但这是另一种测试数字是否为素数的方法。作为复习，素数是大于 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")
于 2018-10-26T06:20:08.110 回答
0
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 到数字的平方根。
于 2020-07-22T08:03:26.437 回答
0
### 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
于 2021-07-04T08:12:39.863 回答
0
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))
于 2018-03-27T20:07:28.413 回答
0
我们可以使用 java 流在 O(sqrt(n)); 中实现这一点。考虑 noneMatch 是一个 shortCircuiting 方法，当发现不需要确定结果时停止操作：
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");
于 2018-10-26T06:47:22.197 回答
0
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;
}
于 2018-04-19T17:18:33.523 回答
0
查找范围内的一个或多个数字是否为素数。
#!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.
于 2018-03-23T11:38:43.393 回答
0
与前面提到的AKS算法类似的想法
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;
}
于 2017-08-14T19:30:14.820 回答
0
在 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))。也许有人觉得它有用。
于 2018-10-29T19:46:30.487 回答
-2
当我必须进行快速验证时，我根据低于输入平方根的数字之间的基本除法编写了这个简单的代码。
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。
于 2020-06-27T02:56:37.753 回答