いくつかの簡単な素数を求めるアルゴリズムの複雑さの分析
， ， 。 ： ， ， 。 Ｏ(n) O(n**0.5). 100000 ， ：
１． ， ， ：print(2)for i in range(3,100000,2): for a in range(3,int(i**0.5)+1,2): if i%a == 0: break else: print(i,end = ' ')'''
* (0.5*n*((n**0.5)+1)/2)， Ｏ(n**1.5)
２． ： ６ ６ ， ：
'''
print(2,3,end = ' ')
n = 100000
i = 5
step = 2
while i<= n:
for j in range(5,int(i**0.5)+1,2):
if j%j == 0:
break
else:
count += 1
i += step
step = 4 if step ==2 else 2
''' ：
１ ， ５ ５ ， ５ ，j 0.4*n*((n**0.5+1)*0.4)。 ５， （１，３，７，９）， ４/10=0.4, 。 56%(0.5**2/0.4**2-1=0.56)。
２ ， ５ 。 ，30~60 ，６ （36,42,48,54,60）, （35,37,41,43,47,49,53,55,59,61）, ５ （35,55）, ３０ ， ８ ， (n/30*(5*2-2))*(n**0.5+1)*0.4=4/15*n*(n**0.5+1)*0.4。 １ ， ２ 50%( ， 0.4/(4/15), 0.4/(4/15)-1=0.5)。
， 。