麻省理工学院公开课：计算机科学及编程导论习题1
发布时间
阅读量：
阅读量
习题1：
编辑一个程序，显示出第1000个质数。
质数的特性是只能被1和自己整除，所以所有算法都由此引开。
因为一开始漏看了“th”，所以以为是1~1000里面的质数...
这是一种算法，这两种的效率差不多：
print "2",
for x in range(3, 1001):
y = 2
while x % y != 0 and x > y:
y = y + 1
if y == x:
print x, print "2",
for x in range(3, 1001):
for y in range(2, x):
if x % y == 0:
break
elif y == x - 1:
print x,这种算法需要算出所有数字的余数，所以最慢，但是思考起来最简单的。
for x in range(1, 1001):
count = 0
for y in range(1, x + 1):
if x % y == 0:
count += 1
if count == 2:
print x,这种算法源自他人的作品，在性能上具有显著优势；然而其中蕴含着深奥的数学理论；或许未来某个时刻会彻底弄懂。
i = 2
while(i < 1001):
j = 2
while(j <= (i/j)):
if not(i%j): break #if i%j == 0
j = j + 1
if (j > i/j) : print i,
i = i + 1下面开始正式解题，最终得出第1000个是7919。
x = 3
order = 1
while x > 2 and order < 1000:
count = 0
for y in range (1, x+1):
if x % y == 0:
count += 1
x += 1
if count == 2:
order += 1
if order == 1000:
print x-1另外一种算法：
x = 3
order = 1
while x > 2 and order < 1000:
y = 2
while x % y != 0 and x > y:
y = y + 1
if y == x:
order = order + 1
if order == 1000:
print x
x = x + 1或者
x = 3
pn = [2]
while x > 2 and len(pn) < 1000:
y = 2
while x % y != 0 and x > y:
y = y + 1
if y == x:
pn.append(x)
x = x + 1
print pn[-1]第一种因为计算了全部的余数值而导致整体运算时间较长，在此情况下其运算速度较之则明显较慢；而相比之下，则是仅计算了一部分余数值的情况下完成任务的速度更快捷高效；因此在时间效率上存在较大的差距；具体而言前者需要花费2.89秒即可完成任务而后者只需0.61秒就能快速得出结果
习题2：
将从2到n的所有质数的指数进行累加，并将这一总和与给定数值进行比较分析；其指数之和相对于给定数值的比例，在数值增大时接近1；请提供不同数值供进一步分析。
from math import log
n = int(input("Please enter a number for variable n: "))
log_sum = log(2)
for x in range(3, n+1):
y = 2
while x % y != 0 and x > y:
y = y + 1
if y == x:
log_sum = log_sum + log(x)
print "sum = %r" % log_sum
print "n = %r" % x
print "ratio = %r" % (log_sum/x)如果做成模块的话
def get_prime(x):
x = int(x)
if x == 1:
return False
elif x == 2:
return True
else:
for y in range(2, x):
if x % y == 0:
return False
break
elif y == x - 1:
return True
from math import log
n = int(input("Please enter a number for variable n: "))
log_sum = 0
for x in range(2, n+1):
if get_prime(x):
log_sum = log_sum + log(x)
print "sum = %r" % log_sum
print "n = %r" % n
print "ratio = % r" % (log_sum/n)全部评论 (0)
还没有任何评论哟~