判断素数，高效率的写法。

wei_Y

判断素数，完全没有思路啊。
有没有什么神奇的模块可以用。。

hellofdy

如果你数学好。。。请你看这篇文章。。。
http://blog.csdn.net/liukehua123/article/details/5482854

wei_Y

hellofdy 发表于 2014-9-20 17:21
如果你数学好。。。请你看这篇文章。。。
http://blog.csdn.net/liukehua123/article/details/5482854

没大看懂，谢谢咯。

牡丹花下死做鬼

判断素数啊 长久来考虑的话
先用筛法弄出一个素数数组 如 【1~10W】
然后就
循环从2开始 用你那个数取余数 数组里的素数 直到你的那个数的平方根为止

bevin

1. def isprime(n):
   
2.     for i in range(2,(int((n+1)**0.5))+1):
   
3.         if n % i == 0:
   
4.             return False
   
5.     return True

复制代码

n要为>=2的整数

破渔网兜兜

bevin 发表于 2014-9-24 13:04
n要为>=2的整数

range(2,(int((n+1)**0.5))+1)
这个是啥意思，不是素数的定义是

检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于根号N的所有素数去试除，若均无法整除，N则为素数

不是写成range(2,(int(n**0.5))+1)就行了么，为什么要写n+1呢

wei_Y

bevin 发表于 2014-9-24 13:04
n要为>=2的整数

终于解决了。

破渔网兜兜

bevin 发表于 2014-9-24 13:04
n要为>=2的整数

没加好友，不能@,先放这里了http://bbs.fishc.com/forum.php?m ... id=50263&ctid=7

wei_Y

破渔网兜兜 发表于 2014-9-24 14:36
range(2,(int((n+1)**0.5))+1)
这个是啥意思，不是素数的定义是
不是写成range(2,(int(n**0.5))+1)就行 ...

多几个数没差别吧，就是多除了几个。

青蛙星

减少 除数n 的选取个数就行了。
比如 n = 4，既然4 能被 2 整除，也就是说 一个连2都无法整除的数，也无法被4整除，该直接使用5（素数，作为素数无法被整除，且所有的 合数都能被 素数表示）。因此我们使用 素数作为除数可以极大提高效率。另外选择的素数也不能大于被除数，因为无法 大数整除小数。
因此采用 素数数组作为除数是一种高效的选择。

wei_Y

青蛙星 发表于 2014-9-25 11:26
减少 除数n 的选取个数就行了。
比如 n = 4，既然4 能被 2 整除，也就是说 一个连2都无法整除的数，也无法 ...

其实我本来想筛选1000以内的素数，用这种方法等于是直接有结果了，所以才问的另外的方法。

青蛙星

wei_Y 发表于 2014-9-25 11:35
其实我本来想筛选1000以内的素数，用这种方法等于是直接有结果了，所以才问的另外的方法。

你没有注意到一件事吗？如果是事先列出的素数数组是没有价值的。
换句话说，这个数组是要增长的，随着你找到的素数越多这个数组就越大，你每找到一个素数就放进去，以备计算下一个数是否是素数。

wei_Y

青蛙星 发表于 2014-9-25 17:16
你没有注意到一件事吗？如果是事先列出的素数数组是没有价值的。
换句话说，这个数组是要增长的，随着你 ...

嗯，我是想的没有事先列出的素数然后去判断一下。

网络学习

期待程序出现  

chensen

顶顶啊啊啊啊:cry

1012662902

你在网上查  筛选法素数    这个应该是最快的了

wei_Y

1012662902 发表于 2014-9-27 11:54
你在网上查  筛选法素数    这个应该是最快的了

谢谢哦，已经解决了。

会飞的鱼2016

def sushu(n):
        import math
        for i in range(2,int(math.sqrt(n)+1)):
                if n % i == 0:
                        print(n,'is not sushu')
                        break
        else:
                print(n,'is sushu')