Python：每日一题 效率题

新手·ing

啊哈哈哈哈，十月一来了，楼楼终于可以回归几天了~

今日题目：判断一个数是否为质数。但是！！！这是一道效率题，效率越高越好，方法多得是，只不过效率有差别罢了。

题目很简单，准备围观大佬~

基本解法：

游客，如果您要查看本帖隐藏内容请回复

itertools：

游客，如果您要查看本帖隐藏内容请回复

math：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

1. is_prime = lambda n: True if n in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67} else all(False for p in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67} if pow(p,n-1,n) != 1)

复制代码

基本上10**15以内都是毫秒级别的

wyh2006

from math import factorial

def prime(x):
    return factorial(x-1)%x == x-1

solomonxian

我只知道可以先用费马小定理去掉大部分合数，
后面怎样更快就不清楚了

1. def fun(n):
   
2.     if n == 2:
   
3.         return True
   
4.     elif n > 2 and pow(2, n-1, n)==1:
   
5.         for i in range(2, int(n**0.5)+1):
   
6.             if n % i :
   
7.                 return False
   
8.         else:
   
9.             return True
   
10.     else:
    
11.         return False

复制代码

新手·ing

jerryxjr1220 发表于 2017-9-29 21:57
基本上10**15以内都是毫秒级别的

zhll912

你们都是大礼

SixPy

你们都是大礻申

suloman

jerryxjr1220 发表于 2017-9-29 21:57
基本上10**15以内都是毫秒级别的

求解释  。。 写一行看不太懂

jerryxjr1220

suloman 发表于 2017-9-30 12:53
求解释  。。 写一行看不太懂

http://bbs.fishc.com/forum.php?mod=viewthread&tid=88904&mobile=2

a63521557

了解一下

shihuijun

大神的年圻

AsnFuyy

1

过去吧

学习

wujifu333

学习

stars_ice

每天开心学习python

lemon1953

看看

一刹那

先看看！

淡淡的幸福

楼主辛苦

Winger

学习

zzystar

萌新求解中