python语言 超级素数

Python012

python语言 超级素数,第1张

# -*-coding:utf8-*-

#py3

import math

def Prime(n):  #判断n是不是素数

    if n==1:

        return False

    if n==2:

        return True

    t=int(math.sqrt(n)+1)

    for i in range(2,t):

        if n%i==0:

            return False

    return True

if __name__=='__main__':

    s=0 #素数和

    k=0 #个数

    for i in range(100,10000):

        t=i

        while t>1 and Prime(t):#t若是素数且大于1

            t=int(t/10)    #继续去掉低一位.直至t=0或t不是素数

        if t==0:   #该数是所求

            print(i)#测试使用,仅供观察,可以去掉

            s+=i #求和

            k+=1 #计数器加1

    print(s,k)   #输出结果

结果:

i = 2  

while i <= 100:

    j = 2

    while j <= i / j:         #难点1

        if i % j == 0:

            break           #如果提前提出，j的值<= i / j

        j = j + 1

    if j > i / j:            #难点2

        print(i, end=' ')

    i = i + 1

其实代码每一句都很简单，就不一一注释了，其实难的是思路。主要是两个地方对J变量的判断

A:while循环，一种常见的是j<=sqrt(i),用这个数的开方（根号）来指定搜索上限，这是因为：

一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)——所以只要搜索到根号的地方就可以了，提高了速度。

用i/j的方式是sqrt的一种变种，j<=sqrt(i)，由于i>j>1，两边平方后不等式仍然成立

j^2<=i      两边除以j就变成了j <= i / j

B:第二处，根据j的数值来判断i是否是素数。当在循环中找到i % j == 0的情况，循环会提前退出，导致j < i / j——说明不是素数；如果循环没有提前退出，说明i是素数，这时j的值>i / j