素数质数 Prime number

素数，又称质数，英语：Prime number

指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。如：

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113

1	2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113

大于1的自然数若不是素数，则称之为合数，英语：Composite number。

输入一个数，计算是不是素数， python代码如下，其中有两个函数都是可以计算，但第二个快一些，比如输入123456789987654321，第一个要用360秒，第二个一秒不到，因为这个数可以被3整除，第二个函数有做除3的检查。参考了：http://stackoverflow.com/questions/15285534/isprime-function-for-python-language

import time

def isPrime(n):
    if n==2 or n ==3: return True
    if n%2==0 or n<2:
        print '\t', 2
        return False
    for i in range(3, int(n**0.5)+1, 2):   #only odd numbers
        if n%i == 0:
            print '\t', i
            return False
    return True

def is_prime(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2:
        print '\t', 2
        return False
    if n<9: return True
    if n%3 == 0:
        print '\t', 3
        return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        #print '\t', f
        if n%f == 0:
            print '\t', f
            return False
        if n%(f+2) == 0:
            print '\t', f+2
            return False
        f +=6
    return True

n = int(input('Input a number to check if prime:'))
t1 = float(time.time())
while n != None:
    #if isPrime(n):
    if is_prime(n):
        print "It is a prime"
    else:
        print "Not a prime"
    t2 = float(time.time())
    print int(t2-t1), "s used."
    n = int(input('Input a number to check if prime:'))
    t1 = float(time.time())

import time

def isPrime(n):

if n==2 or n ==3: return True

if n%2==0 or n<2:

print '\t', 2

return False

for i in range(3, int(n**0.5)+1, 2): #only odd numbers

if n%i == 0:

print '\t', i

return False

return True

def is_prime(n):

if n==2 or n==3: return True

if n%2==0 or n<2:

print '\t', 2

return False

if n<9: return True

if n%3 == 0:

print '\t', 3

return False

r = int(n**0.5)

f = 5

while f <= r:

#print '\t', f

if n%f == 0:

print '\t', f

return False

if n%(f+2) == 0:

print '\t', f+2

return False

f +=6

return True

n = int(input('Input a number to check if prime:'))

t1 = float(time.time())

while n != None:

#if isPrime(n):

if is_prime(n):

print "It is a prime"

else:

print "Not a prime"

t2 = float(time.time())

print int(t2-t1), "s used."

n = int(input('Input a number to check if prime:'))

t1 = float(time.time())

github path: https://github.com/allenmo/python_study/blob/master/049_is_prime.py

Post Views: 2,193