小开

根据维基百科，埃拉托斯特尼筛法有复杂度 ABC0，需要 O(n)内存——所以如果你不是在测试特别大的数字，这是一个非常好的开始。

小开

最小的记忆? 这不是最小的，但是朝着正确的方向迈出了一步。

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的定义。

小开

通用素数测试的最快算法是 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数字)并进行二进制搜索。这是迄今为止我实现过的最快的测试，唯一的缺点是范围有限。

小开

如果 a是质数，那么代码中的 while x:将永远运行，因为 x将保持为 True。

那为什么 while在那里？

我认为您想在找到一个 factor 时结束 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"

小开

有许多有效的方法来测试素数(这不是其中之一) ，但是您编写的循环可以用 Python 简洁地重写:

def is_prime(a):
return all(a % i for i in xrange(2, a))

也就是说，a 是素数，如果所有介于2和 a 之间的数字(不包括在内)在分成 a 时都给出非零余数。

小开

如果只有几个查询，这是查看数字是否为素数的最有效方法。如果你问很多数字是否是素数，试试埃拉托斯特尼筛法。

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

小开

一个相当简单和简洁的蛮力解决方案来检查一个数字 N 是否为素数: 简单地检查是否有任何 N 的除数从2到 N 的平方根(参见为什么给你如果感兴趣)。

下面的代码与 Python2和 Python3兼容:

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))。

如果你正在寻找更快的算法来检查一个数字是否是质数，你可能会对以下内容感兴趣:

寻找素数 & 证明素数 : 对最著名的素数测试及其历史的简要概述和解释。
概率素性测试(Wikipedia) : 如果没有通过，这些测试可以很容易地被合并到上面的代码中，这样就可以跳过暴力测试，例如这个问题的重复这个绝妙的答案。
快速确定性初始测试(Wikipedia)
这个问答列出 N 以下所有素数的最快方法与 pyprimesieve库一起。

实施说明

您可能已经注意到，在 Python 2兼容的实现中，我将 itertools.count()与 itertools.islice()结合使用，而不是简单的 range()或 xrange()(旧的 Python 2 发电机范围，在 Python 3中是默认的)。这是因为在 CPython 2 xrange(N)中，对于一些 N，N > 2⁶³-1(或 N > 2itertools.islice()0-1，取决于实现)产生一个 OverflowError。这是一个不幸的 CPython 实现细节。

我们可以使用 itertools来克服这个问题。由于我们使用 itertools.count(2)从 2计数到无穷大，我们将在 sqrt(n) - 1步后到达 sqrt(n)，并且我们可以使用 itertools.islice()限制生成器。

小开

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 + + 实现

小开

巨蟒3:

def is_prime(a):
return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))

小开

与前面提到的算法相似

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;
}

小开

查找范围内的数字是否为质数。

#!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.

小开

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))

小开

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;
}

小开

现在去参加派对已经太晚了，但希望这能有所帮助。如果你正在寻找大质数，这是相关的:

为了测试大的奇数，你需要使用 Fermat-test 和/或 Miller-Rabin 检验。

这些测试使用模幂运算，这是相当昂贵的，对于 n位幂运算，您至少需要 n大整数乘法和 n大整数除法。这意味着模幂运算的复杂度是 O (n3)。

所以，在使用大炮之前，你需要做相当多的审判部门。但是不要天真的去做，有一个快速的方法。首先，将你用来表示大整数的字母乘以所有的素数。如果你使用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的几率不是质数(更有可能是你的硬件故障...)。

小开

我有一个质数函数，它直到(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()函数只是处理一系列的数字，如果它看到0或者 False，它就返回 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不被认为是质数。

我希望这有所帮助:)

小开

在 Python 中:

def is_prime(n):
return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

从数学形式主义到 Python 的更直接的转换将使用 全部(n% p! = 0...)，但是这需要对 p 的所有值进行严格的计算。如果找到 True 值，则没有版本可以提前终止。

小开

素数的最佳算法

 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
}

小开

可以使用 symy 。

import sympy


sympy.ntheory.primetest.isprime(33393939393929292929292911111111)


True

医生给的。第一步是寻找微不足道的因素，如果找到这些因素，就可以快速返回。接下来，如果筛子足够大，在筛子上使用二分法搜索。对于小数，一组确定性的 Miller-Rabin 检验是用已知在其范围内没有反例的碱基进行的。最后，如果数字大于2 ^ 64，则执行强 BPSW 测试。虽然这是一个可能的基本检验，我们相信反例的存在，没有已知的反例

小开

以前的大多数答案都是正确的，但是这里还有一个测试的方法，可以看到一个数字是质数。作为复习器，质数的整数大于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")

小开

我们可以在 O (sqrt (n))中使用 java 流来实现这一点; 考虑到 noneMatch 是一个 short Circuiting 方法，当发现不需要确定结果时，它会停止操作:

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");

小开

在 Java-8流和 lambdas 的帮助下，它只需要几行代码就可以实现:

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))。也许有人发现它有用。

小开

我比较了最流行的建议的效率，以确定一个数字是否为质数。我在 ubuntu 17.10上使用了 python 3.6; 我测试的数字高达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))

This answer used some kind of while loop:

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

This answer included a version with a for loop:

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

And I mixed a few ideas from the other answers into a new one:

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

Here is my script to compare the variants:

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()

小开

对于大数，您不能简单地检查候选数 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!

如果你正在测试随机整数，你可能想先测试候选数是否可以被任何小于1000的素数整除，然后再调用 Miller-Rabin。这将帮助您过滤掉明显的非素数，比如10444344345。

小开

素数是任何只能被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除，而且还可以被1除，那么它就是一个合数。

变量 i的初始值必须是2，因为素数和复合数都可以均匀地除以1。

    for (let i = 2; i < number; i++)

出于同样的原因，i小于 number。素数和合数都可以自行均分。因此没有理由去检查它。

然后我们检查变量是否可以通过使用余数运算符进行均匀分配。

    if (number % i === 0) {
return false;
}

如果余数为零，则意味着 number可以被均匀分配，因此是一个合数，返回 false。

如果输入的数字不满足条件，这意味着它是一个素数，函数返回 true。

小开

当我必须做一个快速的验证，我写这个简单的代码基于数字之间的基本划分低于平方根的输入。

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。

小开

让我为你推荐一个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
}

小开

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到数字的平方根。

小开

### 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

小开

最佳解决方案

我不确定我是否理解 Time complexity: O(sqrt(n))和 Space complexity: O(1)在这方面的概念，但函数 prime(n)可能是 fastest way (least iterations) 计算一个数是否是任意大小的素数。

Https://github.com/ganeshkbhat/fastprimenumbers

这可能是互联网上最好的解决方案二零二二年三月，欢迎市民提供意见及使用。

同样的代码可以应用于任何语言，比如 C，C + + ，Go Lang, Java、 .NET、 Python、 Rust 等具有相同的逻辑和性能好处。这是非常快的。我以前从未见过这个实现而且是在本地完成的。

如果你正在看的速度和性能这里是 """BEST"""有希望的解决方案，我可以给出:

N = = 100000的最大迭代数为16666，而不是常规的100000 方式

代码也可以在这里找到: https://github.com/ganeshkbhat/fastprimecalculations

如果您使用它为您的项目，请花2分钟您的时间通过让我知道通过发送电子邮件，或登录主题为 [User]的 Github 问题，或 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;

检查 Prime 的 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万次迭代

第一次:

isPrimeConventionalWayArr:  1749.97224997225
isPrimeSquarerootWayArr:  1835.6258356258356
primeArr (suggested):  475.2365752365752
isprimeAKSWayArr:  1177.982377982378

第二次:

isPrimeConventionalWayArr:  1803.141403141403
isPrimeSquarerootWayArr:  2184.222484222484
primeArr (suggested):  572.6434726434726
isprimeAKSWayArr:  1403.3838033838033

第三次:

isPrimeConventionalWayArr:  1876.941976941977
isPrimeSquarerootWayArr:  2190.43299043299
primeArr (suggested):  569.7365697365698
isprimeAKSWayArr:  1449.4147494147494

第四次:

isPrimeConventionalWayArr:  1873.2779732779734
isPrimeSquarerootWayArr:  2177.154777154777
primeArr (suggested):  590.4243904243905
isprimeAKSWayArr:  1401.9143019143019

第五次:

isPrimeConventionalWayArr:  1891.1986911986912
isPrimeSquarerootWayArr:  2218.093218093218
primeArr (suggested):  571.6938716938716
isprimeAKSWayArr:  1397.6471976471976

第六次:

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

如何建立到极限 N 为止的最紧映射 n → isprim (n) ？