判断素数引发的算法思考

看到一道算法题，要求判断出1000以内的素数

素数嘛 就是只能被自己整除或者被1整除

最笨的方法是从1判断到那个数，聪明点的方法是从3判断到那个数的平方根。

于是我就想，这个要是纯理论的算法 肯定是无可厚非的 第二种是最优算法。那换个角度思考

要是这个算法是实际应用中需要的呢。就是有这么一个业务 用户给定一个数 然后判断其是否为素数。

当这个是业务而不是算法的时候 我就产生了一个很怪的想法。为何不把这些素数都存在某一个文件上

如xml，然后运行前先load出来 判断的时候只是简单的判断其是否能被2整除，不行的话用二分法来在文件

load好的数组中查找即可。

显然存在这一个问题 数字超过了1000怎么办，也就是超过了你文档中储存的最大数字时候怎么办？

我认为那个时候再用最优算法去计算。[align=left][/align]

也就是说，把问题当作业务而不是算法来处理的时候 就存在一个概率问题了。如果在概率统计上能够保证

用户输入的数字大于1000的可能性很小的时候 使用这种伪算法是否更高效一些呢？

评论

6 楼 suifeng 2009-02-12  

给出了一种解决问题的途径, 是一种打破常规的方法.
很有借鉴价值.

5 楼 duanaiguo 2008-08-19  

没有纯理论算法，能称为算法的都是要应用在实际中的，当然对于素数我所知道的更简单的算法为筛法，即去掉非素数的（这个很容易比如从2开始他的所有倍数肯定不是素数），剩下的全是素数。相对加法和乘法算平方根是很复杂的运算，这些教科书上一般都会讲到，大学的课程也不是百无一用，理论联系实际还是一大法宝啊。算法没有说明不能缓存。

4 楼 王者之剑 2008-08-13  

当然是要存起来的，别说1000了，1000万也可以存

3 楼 iamzealotwang 2008-08-13  

引用

数学中函数的定义是一个集合到另一个集合的映射（Map），这种纯的函数，本身不会保存任何状态，任何时候给出确定的参数都有确定不变的结果，所以该函数可以被缓存为一个Map

这个话的确很有哲理的样子。。。。不过我没有明白您要说的是什么意思

2 楼 neusoft 2008-08-13  

理论与工程的区别，大概就在于此吧

1 楼 ShiningRay 2008-08-13  

数学中函数的定义是一个集合到另一个集合的映射（Map），这种纯的函数，本身不会保存任何状态，任何时候给出确定的参数都有确定不变的结果，所以该函数可以被缓存为一个Map