Exercise Solution by Students

题目1

这里只记录了一下代码，和简单的注释~
while True:
    print("Please input two num ...")
    a,b = raw_input().split(" ")
    a = int(a)
    b = int(b)
    # 输入0，0则退出程序
    if a == 0 and b == 0:
        break
    # a >= b则重新输入，即重新开始此循环
    elif a >= b:
        print("Error,Please input again:")
        continue
    # 如果上述两种例外都排除，则程序继续向下执行
    # 遍历a和b中间的每一个数
    for i in range(a+1, b):
        # 先假定它是素数，下面开始检验
        flag = True
        # 1和非正整数都不是素数
        if i <= 1:
            flag = False
        else:
            for j in range(2, int(i**0.5)+1): #循环上限是i**0.5，在range中要加1
                if i % j == 0:
                    flag = False
                    break
        # 输出素数
        if flag:
            print (i)

题目2

初版：

import math
import time
x=time.clock()    #开始计时，用于检验程序运行时间，与作业要求无关
i=2
count=0           #count在这里用来查一共输出了多少回文素数，用于检测，与作业要求无关
while i <10000000000:
    if i!=2 and i%2==0:     #如果i是2的倍数且不是2本身，那么自加1后由continue重新回到循环开始，进行新的判断
        i+=1
        continue
    if i!=5 and i%5==0:     #如果i是5的倍数且不是5本身，那么自加1后由continue重新回到循环开始，进行新的判断
        i+=1
        continue
    a=str(i)                
    if a==a[::-1]:          #判断是否是回文，在判断是回文的基础上再进行是否是素数的检测
        if i!=11 and len(str(i))%2==0:  #因为回文素数除了11之外都是偶数长度的，如不满足即进入到下一个数量级，回循环起始
            i=10**len(str(i))
            continue
        j=0
        for k in range(3,int(math.sqrt(i))+1,2):   #被除数只用基数即可，因为偶数i都被过滤掉了
            if i%k==0:
                i+=1
                j+=1
                break
        if j==0:
            count+=1
            print str(i),
    i+=1
y=int(time.clock()-x)          #时间差
print count
print y

解析：无脑版，直线逻辑一波流，当x小于10的10次幂的时候先排除除了2和5以外所有他们的倍数进行一个简陋的初筛选，然后通过比较该数字变成字符串之后是否是回文引出接下来的素数判断：但判断之前先查看该数字是否为偶数回文但不等于11，如果是pass掉，不是的话再进入到素数判断阶段。跑前10的8次幂需要6秒，跑前10的10次幂需要786秒，效率较低。

最终版：

import math
import time
x=time.clock()
def determine_prime(number):
    for s in p:
        if s<=int(math.sqrt(number)):
            if number%s==0:
                return False;
        else:
            break
    return True
        
def primes2(n):
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]
            
print '2 3 5 7 11',
count=0
p=primes2(10**6)
r=[[0,9,10],[0,99,100],[0,999,1000],[0,9999,10000],[0,99999,100000]]
for row in range (0,5):
    for j in range(1,10,2):
        if j==5:
            continue
        for i in range(r[row][0],r[row][1]+1):
            half=j*r[row][2]+i
            string=str(half)[:-1]+str(half)[::-1]
            number=int(string)
            if determine_prime(number)==True:
                count+=1
                print str(number),
y=int(time.clock()-x)
print y
print count

分析：优化的地方有：1.关于回文，不是遍历，而是我自己造10的12次幂之内的回文数，然后造完之后再判断是否是素数，有目的地造要比遍历效率高很多，这个想法的来源是某天打开的无数关于素数和回文的问题的网页里有个论坛的网友用c语言实现的。2.关于素数判断，自己实在想不出来什么高效算法，百度和google之后采用了埃拉脱斯特尼筛法，然后由于要处理数量级比较大，所以把前10的6次幂之内的素数储存在list里面，在进行7次幂到12次幂之间的素数判断的时候直接除list里面储存的素数，但是我是在7到12次幂判断的时候处以所有list里面小于根号该数的所有素数，但其实遍历除效率还不是很高，还有优化空间，不过没弄出来。现在的这个跑10的12次幂需要964秒，比上一个快了两个数量级