求质数
##############求质数2import datetimestarttime=datetime.datetime.now()####开始时间print(2,end=' ')count=1for i in range(3,100000,2): if i>10 and i % 5 ==0: continue for j in range(3,int(i**(0.5)+1),2): if i % j == 0: break else: count+=1 print(i,end=' ')print('~~~~~~~~~~')print(count)print(datetime.datetime.now()-starttime)####运行程序所用时间 另一种方法
#############求质数3flag1=Falseflag2=Falsefor i in range(6,100,6): e=int(math.sqrt(i)+2) for j in range(3,e,2): if (i-1)%j==0 and not flag1: flag1=True if (i+1)%j==0 and not flag2: flag2=True if flag1 and flag2: break if not flag1: print(i-1) if not flag2: print(i+1)
比较以上两种算法的时间
start=datetime.datetime.now()for i in range(10): count1=0 # print(2,3,end=' ') for i in range(6,100000,6): flag1=False flag2=False e=int(math.sqrt(i))+2 for j in range(3,e,2): if not flag1: if (i-1)%j==0: flag1=True if not flag2: if (i+1)%j==0: flag2=True if flag1 and flag2: break if not flag1: #print(i-1,end=' ') count1+=1 if not flag2: #print(i+1,end=' ') count1+=1print('~~~~~~~~~~~~!',count1,datetime.datetime.now()-start)start2=datetime.datetime.now()for i in range(10): #print(2,end=' ') count2=0 for i in range(3,100000,2): if i>10 and i % 5 ==0: continue for j in range(3,int(i**(0.5)+1),2): if i % j == 0: break else: count2+=1 #print(i,end=' ')print('~~~~~~~~~~~!',count2,datetime.datetime.now()-start2)
求质数，使用列表，所有合数都是质数的乘积，将所有质数加入列表，通过列表检测，注意边界！
检测到开平方处。原理类似于加法的一半在中间，乘法的中间在开方处，一旦超过，就是重复测试。
l=[2]#求质数4for i in range(3,100,2): e=i**(0.5) for j in l: if i%j==0: break if j>e: l.append(i) breakprint(l,len(l))
这是计算质数，用奇数测试的方法，不用列表
count=1###求质数5print(2,end=' ')for i in range(3,100,2): flag=False for j in range(3,int(i**(0.5))+1,2): if i%j==0: flag=True break if not flag: print(i,end=' ') count += 1print('~~~~~~~',count)
质数有一条特性，质数在大于3后，所有质数都位于6的倍数左右两侧，可以通过列表检测提快速度
l=[2,3]for i in range(6,100,6): flag1=False flag2=False###求质数6 e1=(i-1)**(0.5)+1 e2=(i+1)**(0.5)+1 for j in l: if flag1: break if j>e1: break if (i-1)%j==0: flag1=True for j in l: if flag2: break if j>e2: break if (i+1)%j==0: flag2=True if flag1==False: l.append(i-1) if flag2==False: l.append(i+1) #print('~~~',l) print(l,len(l))
以上方法，可以看到，非常长，不够优雅，有另一种改变步长的方法，代码较好看。。（计算量相同）
count=2w=5step=2print(2,3,end=' ')while w<100: e=w**(0.5) for i in range(3,100,2): if w%i==0: break if i>e: print(w,end=' ') count+=1 break w+=step step=(2 if step==4 else 4)print('`````',count) 以上这种方法没有使用列表，用的是6的倍数两侧的数与奇数取偶。
以下的方法是一种不断改变步长，求质数的方法，使用了列表。
w=5###求质数8step=2primenumbers=[2,3]while w<100: e=w**(0.5) for i in primenumbers: if w%i==0: break if i>e: primenumbers.append(w) break w+=step step=(2 if step==4 else 4)print(primenumbers,len(primenumbers))