求职 # 每日一道面试题 # 判断 101-200 之间有多少个素数，并输出所有素数
要求
- 写出分析思路
- 用 Python 或者 Java 实现
提示：质数又称素数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
count,t=0,list()
for i in range(101,201):
for j in range(2,i/2):
if i%j==0:
break
else:
count+=1
t.append(i)
else:
print count
print t
不换药
count,t=0,Array.new
(101..201).each do |i|
(2..i/2).each do |j|
break if i%j==0
if j==i/2
count+=1
t.push i
end
end
end
puts count
p t
还要补一刀
print [i for i in range(101,201) if all([i%j for j in range(2,i/2)])]
分析思路
- 判断是否是素数，是就输出 (质数（prime number）又称素数，有无限个。质数定义为在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数。)
- 范围 101-200
### python
import math
def is_prime(number):
if number > 1:
if number == 2:
print(number)
if number % 2 == 0:
pass
#步长为2 可以将2以及所有合数因子给排除掉
for current in range(3, int(math.sqrt(number) + 1), 2):
if number % current == 0:
return False
print(number)
return False
for n in range(101,200):
is_prime(n)
程序分析
判断素数的方法：用一个数分别去除 2 到 sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。
#!/usr/bin/python
# -*- coding: UTF-8 -*-
h = 0
leap = 1
from math import sqrt
from sys import stdout
for m in range(101,201):
k = int(sqrt(m + 1))
for i in range(2,k + 1):
if m % i == 0:
leap = 0
break
if leap == 1:
print '%-4d' % m
h += 1
if h % 10 == 0:
print ''
leap = 1
print 'The total is %d' % h
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
分析思路：
素数算法：朴素判断素数算法（大一的内容）
@Test
public void fun8(){
int i = 1, j = 2;
for (i = 100; i <= 200; i++) {
for (j = 2; j <= i; j++) {
if (i % j == 0) {
break;
}
}
if (i == j) {
System.out.println(i + "是素数");
}
}
}
for m in range(101,201) -->for m in range(101,201,2)
k = int(sqrt(m))
for i in range(2,k + 1):-->for i in range(3,k+1,2)
节约 3/4 的循环时间。
对
MBF
回复
MBF
回复
谢谢你看了我的破代码
我承认确实没怎么理解这个算法,只是记得/2 这种可以减少判断；
至于/2 后还能不能叫"朴素"，这个真不知道，所有有可能有误导,抱歉；
有个建议: 题目出了以后,题主是否应该给个答案；
比如／2 减少了判断,为何减少？ 减少了，是不是用相关的代码，比如 py 的 timeit 测一下;
反正到现在自己对 timeit 结果中的那些参数糊了糊涂，没地方查，也不知道怎么查（不要告诉我 py 文档，
它可没解释 walltime 到底是个啥）；
我老看到测试 xxx 性能,一堆名词只有名字,没有任何解释，你想和他深究吗，深究一句，这个参数到底
描述什么，准完蛋；那是测量，不是测试；
这里不是面试，面试官只管提问题，不管解释，这么做是没有意义的，我觉得是这样；谢谢