質數概念

質數是指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數。

題目

統計所有小于非負整數 n 的質數。

代碼

# -*- coding: utf-8 -*-

'''

質數概念：只能被1和自身整除的數字，叫做質數

'''

import math

import time

class Solution:

''' 暴力的方法，將其對每一個比其小的數進行取余運算

如果任一余數為0。則一定不是質數，否則就是質數。(數字1除外)

'''

def getPrimes(self, n: int) -> list:

Primes_list = []

for i in range(2, n+1):

sign = True

for j in range(2, i):

if i % j == 0:

sign = False

break

if sign:

Primes_list.append(i)

return Primes_list

'''

優化暴力方法，我們可以發現，假如一個數為 9 ，那么其二分之一（4.5）后的數都可以不用進行計算，

因為肯定是有余的 。事實上情況會比這更好一些：對正整數 n ，如果用 2 到 √n 之間(包含邊界)的

所有整數去除，均無法整除，則 n 為質數。

'''

def getPrimes2(self, n: int) -> list:

Primes_list = []

for i in range(2, n+1):

sign = True

for j in range(2, int(math.sqrt(i))+1):

if i % j == 0:

sign = False

break

if sign:

Primes_list.append(i)

return Primes_list

'''

如果 x 是質數，那么大于 x 的 x 的倍數 2x,3x,...一定不是質數。

因此,可以進行將質數標記為1，非質數標記為0.

'''

def getPrimes3(self, n: int) -> list:

isPrimes = n*[1]

Primes_list = []

for i in range(2, n+1):

if isPrimes[i-1]:

Primes_list.append(i)

for j in range(i*i,n+1,i):

isPrimes[j-1]=0

return Primes_list

if __name__ == "__main__":

s = Solution()

time1 = time.time()

result = s.getPrimes(10000)

print(len(result), time.time()-time1)

time2 = time.time()

result2 = s.getPrimes2(10000)

print(len(result2), time.time()-time2)

time3 = time.time()

result3 = s.getPrimes3(10000)

print(len(result3), time.time()-time3)

結果

1229 0.2709805965423584

1229 0.007999658584594727

1229 0.001996278762817383