Python语言的isPrime函数
所以我能够从互联网的一点点帮助解决这个问题，这就是我得到的：
def isPrime(n): for i in range(2,int(n**0.5)+1): if n%i==0: return False return True 但我的问题确实是如何做到这一点，但为什么。 我知道1不被视为一个“主要”数字，即使它是，我明白，如果它在任何范围内划分，它是自动首要的，因此返回False语句。 但是我的问题是在这里打平“n”这个angular色呢？ 非常感谢您的关注
Ps我很缺乏经验，刚刚在一个月前被介绍给编程：S
在互联网上浮动的许多素性testing中，考虑以下主要testing：
def is_prime(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False r = int(n**0.5) f = 5 while f <= r: print '\t',f if n%f == 0: return False if n%(f+2) == 0: return False f +=6 return True
考虑素数5003：
print is_prime(5003)
打印：
5 11 17 23 29 35 41 47 53 59 65 True
行r = int(n**0.5)计算结果为70（5003的平方根为70.7318881411， int()将截断此值）
由于前几个testing，并在循环中间的testing，循环只需要评估每6个数字。
考虑下一个奇数（因为除2以外的所有偶数都不是素数）5005，同样的事情打印：
5 False
限制是自x*y == y*x以来的平方根。函数只需要循环1次就可以发现5005可以被5整除，因此不是素数。 由于5 X 1001 == 1001 X 5 （两者都是5005），我们不需要一直到循环中的1001来知道我们在5中知道什么！
现在，让我们看看你有的algorithm：
def isPrime(n): for i in range(2,int(n**0.5)+1): if n%i==0: return False return True
有两个问题：
- 它不检验
n是否小于2，没有小于2的素数; - 它testing2到n ** 0.5之间的每个数字，包括所有偶数和全部奇数。 由于每个大于2的可被2整除的数不是素数，因此只需testing大于2的奇数就可以加速一点。
所以：
def isPrime2(n): if n==2 or n==3: return True if n%2==0 or n<2: return False for i in range(3,int(n**0.5)+1,2): # only odd numbers if n%i==0: return False return True
好的 – 这会加快30％左右（我以此为基准）
我使用的algorithmis_prime仍然快了两倍，因为只有每第六个整数循环循环。 （我再次以此为基准）。
附注：x ** 0.5是平方根：
>>> import math >>> math.sqrt(100)==100**0.5 True
附注2： 素数testing是计算机科学中一个有趣的问题。
用n**.5 ，你不是平方n，而是取平方根。
考虑数字20; 整数因子是1,2,4,5,10和20.当你用20除以2得到10时，你知道它也可以被10整除，而不必检查。 当你除以4并得到5时，你知道它可以被4和5整除，而不必检查5。
在到达这个中间点之后，你将没有更多的数字来检查你之前没有被认定为因素。 所以你只需要半路看看是否有素数，这个中间点可以用数的平方根来找。
另外，原因1不是质数是因为质数被定义为有2个因子，1和它自己。 即2是1 * 2，3是1 * 3，5是1 * 5。 但1（1 * 1）本身只有1个因子。 因此，它不符合这个定义。
这个问题在一段时间之前就被问到了，但是我有一个更短的解决scheme
isPrime(Number): return 2 in [Number,2**Number%Number]
如果数字是素数而不是2，则math运算总是返回2.但是，如果2是给定的数字，它将被追加到我们正在查找的列表中。
2^5=32 32%5=2 2^7=128 128%7=2 2^11=2048 2048%11=2
等等 …
如果Number是Prime，则isPrime（）返回True，否则返回False。
find数字的平方根是为了提高效率。 例如。 如果我试图找出36的因素，那么可以乘以它自己来形成36的最高数字就是6·7 * 7 = 49。
因此每个36的因子必须乘以6或更小的数字。
下面没有进行浮点运算。 这是更快的，将容忍更高的论点。 你只能走平方根的原因是，如果一个数字有一个大于其平方根的因子，它也有一个小于它的因子。
def is_prime(n): """"pre-condition: n is a nonnegative integer post-condition: return True if n is prime and False otherwise.""" if n < 2: return False; if n % 2 == 0: return n == 2 # return False k = 3 while k*k <= n: if n % k == 0: return False k += 2 return True
def is_prime(x): if x < 2: return False elif x == 2: return True for n in range(2, x): if x % n ==0: return False return True
这是我的方法：
import math def isPrime(n): 'Returns True if n is prime, False if n is not prime. Will not work if n is 0 or 1' # Make sure n is a positive integer n = abs(int(n)) # Case 1: the number is 2 (prime) if n == 2: return True # Case 2: the number is even (not prime) if n % 2 == 0: return False # Case 3: the number is odd (could be prime or not) # Check odd numbers less than the square root for possible factors r = math.sqrt(n) x = 3 while x <= r: if n % x == 0: return False # A factor was found, so number is not prime x += 2 # Increment to the next odd number # No factors found, so number is prime return True
为了回答原来的问题， n ** 0.5 与n的根的平方相同。 您可以停止检查此数字之后的因素，因为合成数字总是小于或等于其平方根。 这比仅仅检查每个n的2和n之间的所有因素要快，因为我们检查的数量更less，这样可以节省更多的时间。
isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])
这里是如何使用它
isPrime(2) == False isPrime(5) == True isPrime(7) == True
要查找您可能使用的所有素数：
filter(isPrime, range(4000)[2:])[:5] => [2, 3, 5, 7, 11]
请注意，在这种情况下，5表示要查找的素数的数量，以及将查找素数的4000个最大范围。
很简单！
def prime(x): if x == 1: return False else: for a in range(2,x): if x % a == 0: return False return True
你写的每一个代码都应该是有效的。对于像你这样的初学者来说，最简单的方法是检查数字“n”从2到（n-1）的可分性。 当你考虑非常大的数字时，这需要很多时间。 平方根方法可以帮助我们以较less的比较次数使代码更快。 阅读devise和algorithm分析中的复杂性。
def is_prime(x): if x < 2: return False for n in range(2, (x) - 1): if x % n == 0: return False return True
int(n**0.5)是您与n (n**2)幂2混淆的sqrt（n）的底板值。 如果n 不是素数，则必须有两个数字1 < i <= j < n ，使得： i * j = n 。
现在，由于sqrt(n) * sqrt(n) = n假设其中之一i,j大于（或等于） sqrt(n) – 这意味着另一个必须小于（或等于） sqrt(n) 。
既然是这样，那么迭代范围[2, sqrt(n)]的整数就足够了。 而这正是发布的代码正在做的。
如果你想成为一个真正的smartass出来，使用下面的单行函数：
import re def is_prime(n): return not re.match(r'^1?$|^(11+?)\1+$',n*'1')
这里可以find“魔法正则expression式”的解释
def fun(N):#prime test if N>1 : for _ in xrange(5): Num=randint(1,N-1) if pow(Num,N-1,N)!=1: return False return True return False
如果数字为素数，则为真，否则为假
我不知道我是否迟到，但我会在这里留下这个帮助未来的人。
我们使用（n）的平方根，即int（n ** 0.5）来减less程序将被迫计算的数字范围。
例如，我们可以做一个试算来testing100的素数。让我们来看看所有100的因数：
2，4，5，10，20，25，50这里我们看到最大的因子是100/2 = 50.所有n都是如此：所有的因数小于或等于n / 2。 如果我们仔细看看因数，我们会看到其中有些是多余的。 如果我们写下不同的列表：
100 = 2×50 = 4×25 = 5×20 = 10×10 = 20×5 = 25×4 = 50×2冗余变得明显。 一旦我们达到了10，这是√100，因子只是翻转，重复。 因此，我们可以进一步消除大于√n的testing因子。
再换一个数字，如16。
它的因数是2,4,8
16 = 2 * 8,4 * 4,8 * 2。
你可以注意到在达到16的平方根4之后，我们重复了8 * 2，我们已经做了2 * 8。 所有数字都是这种模式。
为了避免重复自己，我们从而检验素数到n的平方根。
所以我们将平方根转换为int，因为我们不需要带有浮点数的范围。
阅读wikipedia上的素数testing以获取更多信息。
这个方法比recursion和枚举方法慢，但是使用了Wilson的定理，并且只是一个单独的一行：
from math import factorial def is_prime(x): return factorial(x - 1) % x == x - 1
这是我的np方式：
def is_prime(x): if x < 4: return True if all([(x > 2), (x % 2 == 0)]): return False else: return np.array([*map(lambda y: ((x % y) == 0).sum(), np.arange(1, x + 1))]).sum() == 2
performance如下：
%timeit is_prime(2) %timeit is_prime(int(1e3)) %timeit is_prime(5003) 10000 loops, best of 3: 31.1 µs per loop 10000 loops, best of 3: 33 µs per loop 10 loops, best of 3: 74.2 ms per loop
def is_prime(n): n=abs(n) if n<2: #Numbers less than 2 are not prime numbers return "False" elif n==2: #2 is a prime number return "True" else: for i in range(2,n): # Highlights range numbers that can't be a factor of prime number n. if n%i==0: return "False" #if any of these numbers are factors of n, n is not a prime number return "True" # This is to affirm that n is indeed a prime number after passing all three tests
def isPrime(num,div=2): if(num==div): return True elif(num % div == 0): return False else: return isPrime(num,div+1)
这是我的
import math def is_prime(num): if num % 2 == 0 and num > 2: return False for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True
数字1是一个既不是素数也不是复合数的特例。 欲了解更多信息，请访问： http : //mathworld.wolfram.com/PrimeNumber.html
而且，（n ** 0.5） – >这会给我们“n”的“ 平方根 ”。 由于它是“提高到0.5或1/2的功率”
我们为什么要这么做呢，比如400号：我们可以用a * b的forms来表示
1*400 = 400 2*200 = 400 4*100 = 400 5*80 = 400 8*50 = 400 10*40 = 400 16*25 = 400 20*20 = 400 25*16 = 400 40*10 = 400 50*8 = 400 80*5 = 400 100*4 = 400 200*2 = 400 400*1 = 400
400的平方根是20，我们可以看到，我们只需要检查可分性到20，因为，当'a'达到20时，'b'开始减less…因此，最终我们用小于平方根。
我有一个新的解决scheme，我认为可能会比Python中提到的任何函数都快
它基于这样的思想：N / D = R对于任意的任意数N，除N（如果不是素数）的最小可能数是D = 2，相应的结果R是（N / 2）（最高）。
当D越大，结果R越小ex：除以D = 3的结果R =（N / 3）所以当我们检查N是否可以被D整除时，我们也检查它是否可以被R整除
所以D变大，R变小（D == R ==平方根（N））
那么我们只需要检查从2到sqrt（N）的数字来节省时间，我们只需要检查奇数，因为数字可以被任何偶数整除，它也可以被2整除。
所以顺序是3,5,7,9，……，sqrt（N）。
import math def IsPrime (n): if (n <= 1 or n % 2 == 0):return False if n == 2:return True for i in range(3,int(math.sqrt(n))+1,2): if (n % i) == 0: return False return True
def is_prime(x): if x<2: return False elif x == 2: return True else: for n in range(2, x): if x%n==0: return False return True
有趣的家伙…为什么这么简单的方法这么多的代码行？ 这是我的解决scheme：
def isPrime(a): div = a - 1 res = True while(div > 1): if a % div == 0: res = False div = div - 1 return res
