資工趴趴熊的小天地

一.建立質數表

#假設我們要建立1-100的質數，1為質數，0為合數

max=100#1.建立一個長度為100支陣列
f=[0,1]*(max//2+1)
#這裡f list的第一個數字為第0位，他是偶數，第二個數字為第一位，他是奇數
#f陣列他會遵循著[偶數，奇數...]到你要的長度

f[0]=0;f[1]=0;f[2]=1;f[3]=1#數字中，0為合數，1為合數，2為質數，3為質數，這裡手動輸入，後面就會按照[0,1]的樣式了

h=int(max**0.5)#接下來每一個數字去看他是否有因數，在因數的檢測中，只要檢測到他的中間就好，因為後面就是顛倒而已
for i in range(3,h+1,2):#從數字3開始檢查因數，檢查到中間因數就好，偶數不用檢查，所以2個2個跳
    if(f[i]==1):
        #這裡是說如果我找到的數為質數，將它後面的倍數都修為0
        #eg:f[i]==3時，3是質數為1，那後面的6,9,12,15,18...為0
        for j in range(i*i,max+1,i*2):
            f[j]=0
        
#這裡分三個部份說:
#1.起點為i*i:
#    假設i=5，那5*1=5為質數為1(不是我要的)，
#                5*2=10為偶數為0(不是我要的)，
#                5*3=15在i=3*5時就會被處理完了，不需再處理
#                5*4=20為偶數為0(不是我要的)，
#                5*5=25這裡還沒處理，從這裡開始
#2.終點為max+1，就是到尾吧
#3.中間為i*2
#    如果是i的話，i(奇數)*i(奇數)+i(奇數)會為偶數，不是我要的
#    如果是*2的話，i(奇數)*i(奇數)+2*i(偶數)這樣才對
但在這題中會造成記憶體空間超過



完整碼
max=1000
f=[0,1]*(max//2+1)
f[0]=0;f[1]=1;f[2]=1;f[3]=1
h=int(max**0.5)
for i in range(3,h+1,2):
    if(f[i]==1):
        for j in range(i*i,max+1,i*2):
            f[j]=0
sim=[]
for i in range(1000):
    if f[i]==1:
        sim.append(i)
print(sim)

二.判斷質因數優化方式

def prime(n):  
    return n>=2 and not any(n%i==0 for i in range(2,int(n**0.5+1)))

三.判斷質因數優化方式

def prime(n):#判斷質數
    if (n <= 1): return False
    if (n == 2): return True
    if (n == 3): return True
    if (n == 5): return True
    if (n == 7): return True
 
    if (n % 2 == 0): return False
    if (n % 3 == 0):return  False
    if (n % 5 == 0):return  False
    if (n % 7 == 0):return  False
    d=5
    gap=2
    while(d*d<=n):
        if (n % d == 0):
            return False
        d+=gap
        gap=6-gap
    return True