求2~2000的所有素数.有足够的内存,要求尽量快

ytl

原帖由 haoji 于 2008-9-21 14:57 发表
还是查表快


int myadjust(int shu)
{
   
   static char mytable[]={1,0,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1 ...

题目就是让你生成这张表啊！

ytl

原帖由 cjaizss 于 2008-9-21 15:43 发表

生成这样一张静态的表供C语言使用,我一般还是借助脚本:

#!/bin/awk -f
{
        x=$1;
        printf("static int mytable[]={")
        for(i=0;i

1. 偶数的情况不对
2. 这句循环的上限应该是y: for(j=3;j<=y;j+=2) {

ytl

原帖由 haoji 于 2008-9-22 00:06 发表
看来，在百万以内的数字范围，查表法比其他方法效率要高。


甚至在64位大内存系统上面，在上亿范围的数字内，查表永远效率最高。

跑题了，因为题目是要找出2000以内所有的素数，实际上考的就是生成这样一张表的算法

ytl

原帖由 haoji 于 2008-9-22 10:23 发表


如果为了建立表，2000以内质数的搜索的算法没有必要被讨论，用最笨的搜索法也没关系，时间也不会差到1毫秒。
最关键还是如何方便地建立表，和高效地使用表。
没必要因为楼主的题目而限制了思维。

既然承认最关键是建表，所以不能用查表法。
2000个数不是关键，因为这只是算法题而已，考的是算法。如果不是考察算法，确实没必要被讨论，相信很多数学家早就手工计算过了，直接拿来用就是了，为什么要编程序用计算机搜索？

[ 本帖最后由 ytl 于 2008-9-22 10:40 编辑 ]