作者：Raffeale/于大伟
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
一般正常人的解法是两次循环，假设求小于N的所有素数。一次用N-1之间的所有数去除，如果能被整除这个数肯定不是素数。否则是素数。
这个解题的基本思路：
一个数是否是素数其实不需要去除所有N-1的数，在一个群里有人提出一种方法，只要处以N/2之间的所有数字就可以。经过仔细思考，我发现有更快的方法。只要除以这个数的平方根+1之间的所有的即可。这是为什么？听我慢慢道来。
鉴定x是否为素数，最常用的做饭是个从2开始除，一直除到x-1.那么每当用X/n 的时候，N的值依次为[2,3,4,5,6,7,8,9......x-1] .当我们使用X除以2的时候，如果不能整除，说明了x肯定不能被 X/(X/2)整除，并且X不能被小于x/2的值整除。其实就是小学的数学思想,
例如： 10/5 =2 和 10/2=5的性质是一样的。
那么推理证明 X每当除以一个数的时候，N的范围都在缩小。例如，X/2 后 n的范围应该是 x/2-1 ,x/3后N的范围应该x/3-1,说到这里应该明白了吧。
?那也就是说只要一个数不可以被X/10之内所有的数整除的话就说明这个数是素数。这个算法比那个人提出的要快N倍。经过测试在1000000中找出所有的素数，使用python花费25秒钟左右。估计pypy会非常快。
def primesqrt(n):
result = list()
result.append(2)
result.append(3)
for i in xrange(5,n+1,2):
for j in xrange(2,int(sqrt(i))+2):
#for j in range(2,(i>>4)+1):
if i%j == 0:
break
else:
result.append(i)
return result