返回1000以内的质数

分析

  任何一个合数都可以分解成多个质数相乘的形式，所以只需要判断小于的所有质数是否为的因子。

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