计算质数的两种方法比较以及验证哥德巴赫猜想

计算质数的两种方法

计算小于n以内的质数方法有很多，这里主要对其中两种简单省事的方法做一下比较以及讨论

方法一：开根号取余判断，如果判断10是否是质数，仅需判断10的1/2次方以内是否可以被10取余数为0或者整除）。

import time

def su(num):
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            break
        if i == int(num ** 0.5):
            return num

n = int(input())
nums = [2,3]

start_time = time.time()

for i in range(2,n+1):
    if su(i):
        nums.append(su(i))
print(nums)

end_time =time.time()

print("time:%s" % (end_time-start_time))

方法二：创建布尔类型数组进行判断。首先创建一个全为True的数组，再遍历小于n的每一个数，如果能把2，3，5，7整数或取余数为0，那么将这个下标所对应的True改为False。最后将True所对应的下标输出即为n以内的所有质数。

import time

def su(nums):
    for i in range(2, len(nums)):
        if i not in (2, 3, 5, 7):
            if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                nums[i] = False
    return nums

n = int(input())
nums = [True for i in range(n)]
nums2 = []

start_time = time.time()

su(nums)

for i in range(2, len(nums)):
    if nums[i]:
        nums2.append(i)
print(nums2)
end_time =time.time()

print("time:%s" % (end_time-start_time))

两种方法分析与比较：

在一个数的判断筛选上，方法一会将该数先去根号再遍历取余来判断，方法二通过运算符的方法来判断。对应时间而言方法二优于方法一；
在空间占用上，方法二比方法一多一个数组来存放类型。

练习之：证明哥德巴赫猜想：任何一个偶数都可以是两个质数相加之和，例如：18 = 5+13；；请证明1000以内的偶数都可以实现这个猜想

def su():
    nums = [True for i in range(1000)]
    nums2 = []
    for i in range(2, len(nums)):
        if i not in (2, 3, 5, 7):
            if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                nums[i] = False

    for i in range(2, len(nums)):
        if nums[i]:
            nums2.append(i)
    return nums2

def sum(list):
    num = int(input())
    i,j = 0,len(list)-1
    while(i<j):
        if list[i]+list[j] == num:
            print('%d = %d+%d' %(num,list[i],list[j]))
            break
        if list[i]+list[j] < num:
            i+=1
        if list[i]+list[j] > num:
            j-=1
    else:
        print('error')

sum(su())

利用双指针以及上述的方法而可以很方便的解决这个问题，讲解略。