分析
任何一个合数都可以分解成多个质数相乘的形式，所以只需要判断小于的所有质数是否为
的因子。
def FindPrimeNumbers(n):
prime = []
if(n<2):
return prime
for i in range(2, n+1):
if len(prime)==0:
prime.append(i)
else:
isPrime = True
for j in prime:
if i%j==0:
isPrime = False
break
j += 1
if isPrime:
prime.append(i)
return prime
改进
合数至少包含2个不为1的因子，且若，
，则
，则在小于
的范围内，一定能找到
的一个因子
，因此内层循环只需要循环到小于等于
的地方，且仅在
时取等号。
def FindPrimeNumbers(n):
prime = []
if(n<2):
return prime
for i in range(2, n+1):
if len(prime)==0:
prime.append(i)
else:
isPrime = True
j = 0
while(j<len(prime) and prime[j]<=pow(i, 0.5)):
if i%prime[j]==0:
isPrime = False
break
j += 1
if isPrime:
prime.append(i)
return prime
