免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 求2~2000的所有素数.有足够的内存,要求尽量快
1234下一页
最近访问板块 发新帖
楼主: xiaozhu2007
打印 上一主题 下一主题

[C] 求2~2000的所有素数.有足够的内存,要求尽量快 [复制链接]

haoji

论坛徽章:
0
11楼 [报告]
发表于 2008-09-21 14:57 |只看该作者
还是查表快


  2. int myadjust(int shu)
  3. {
  4.    
  5.    static char mytable[]={
  6.         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,
  7.         1,0,1,0,1,1,1,0,1,1,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,1,1,0,
  8.         1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,
  9.         1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,
  10.         1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,
  11.         1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,
  12.         1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,
  13.         1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,
  14.         1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,
  15.         1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,
  16.         1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,
  17.         1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,
  18.         1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,
  19.         1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,
  20.         1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,
  21.         1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
  22.         1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,
  23.         1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,
  24.         1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,
  25.         1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,
  26.         1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,
  27.         1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,
  28.         1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,
  29.         1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,
  30.         1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,
  31.         1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,
  32.         1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,
  33.         1,1,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,1,1,1,1,1,1,0,1,1,
  34.         1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,
  35.         1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,
  36.         1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,
  37.         1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,
  38.         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,1,1,1,1,1,1,0,
  39.         1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  40.         1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,
  41.         1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,
  42.         1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
  43.         1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
  44.         1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,
  45.         1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,
  46.         1,0,1,1,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,1,1,1,1,1,1,0,1,1,
  47.         1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,
  48.         1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,
  49.         1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,
  50.         1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,
  51.         1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
  52.         1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,
  53.         1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,
  54.         1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,
  55.         1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1
  56.         };

  58.    return mytable[shu];
  59. }



复制代码

[ 本帖最后由 haoji 于 2008-9-21 15:07 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
ytl

论坛徽章:
0
12楼 [报告]
发表于 2008-09-21 15:06 |只看该作者
原帖由 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 ...


题目就是让你生成这张表啊！
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
haoji

论坛徽章:
0
13楼 [报告]
发表于 2008-09-21 15:09 |只看该作者
原帖由 ytl 于 2008-9-21 15:06 发表


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



  2. #include <stdio.h>

  4. int main()
  5. {
  6.   int total=2000;
  7.   int i;
  8.   int t;
  9.   printf("static char mytable[]={1,0,0,");
  10.   for(t=3;t<=total;t++)
  11.   {
  12.     int k=t/2;
  13.     for(i=2;i<=k;i++)
  14.      if((t/i)*i==t)
  15.         break;
  16.     if(i==k+1)
  17.       printf("0",t);
  18.     else
  19.       printf("1",t);
  20.     if(t<total)
  21.       printf(",");
  22.   }
  23.   printf("};\n");
  24.   return 0;
  25. }
复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
14楼 [报告]
发表于 2008-09-21 15:43 |只看该作者
原帖由 haoji 于 2008-9-21 15:09 发表




#include

int main()
{
  int total=2000;
  int i;
  int t;
  printf("static char mytable[]={1,0,0,");
  for(t=3;t

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

  2. #!/bin/awk -f
  3. {
  4.         x=$1;
  5.         printf("static int mytable[]={")
  6.         for(i=0;i<=x;i++)
  7.                 a[i]=1;
  8.         a[0]=a[1]=0;
  9.         y=int(sqrt($1));
  10.         for(j=2;j<=x;j++) {
  11.                 for(k=j+j;k<=x;k+=j){
  12.                         a[k]=0;
  13.                 }
  14.         }
  15.         for(i=0;i<=x;i++)
  16.                 printf("%d,",a[i]);
  17.         printf("};\n");
  18.         exit
  19. }
复制代码

刚才写的有问题，现在改了

[ 本帖最后由 cjaizss 于 2008-9-21 21:26 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
15楼 [报告]
发表于 2008-09-21 15:45 |只看该作者
Haskell的递归功能强大,描述性很强,我也打算用这种方法来描述，可是了解的计算机硬软件语言太多，实在害怕混淆。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
haoji

论坛徽章:
0
16楼 [报告]
发表于 2008-09-21 15:47 |只看该作者
原帖由 cjaizss 于 2008-9-21 15:43 发表

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

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



非常同意，静态的表的生成程序，最主要的还是强调开发效率，对于运行效率则没必要过度强调。
脚本是非常好的选择。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
MMMIX

论坛徽章:
95
程序设计版块每日发帖之星 日期:2015-09-05 06:20:00程序设计版块每日发帖之星 日期:2015-09-17 06:20:00程序设计版块每日发帖之星 日期:2015-09-18 06:20:002015亚冠之阿尔艾因 日期:2015-09-18 10:35:08月度论坛发贴之星 日期:2015-09-30 22:25:002015亚冠之阿尔沙巴布 日期:2015-10-03 08:57:39程序设计版块每日发帖之星 日期:2015-10-05 06:20:00每日论坛发贴之星 日期:2015-10-05 06:20:002015年亚冠纪念徽章 日期:2015-10-06 10:06:482015亚冠之塔什干棉农 日期:2015-10-19 19:43:35程序设计版块每日发帖之星 日期:2015-10-21 06:20:00每日论坛发贴之星 日期:2015-09-14 06:20:00
17楼 [报告]
发表于 2008-09-21 17:35 |只看该作者
原帖由 cjaizss 于 2008-9-21 15:45 发表
Haskell的递归功能强大,描述性很强,

单就这个问题来说，不光递归在起作用，还有更为关键的是 Haskell 的 lazy evolution 的特性，primes 实际是一个 prime stream (所有素数的流)，没有 lazy evolution 这是不可能的。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
ytl

论坛徽章:
0
18楼 [报告]
发表于 2008-09-21 18:08 |只看该作者
原帖由 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) {
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
haoji

论坛徽章:
0
19楼 [报告]
发表于 2008-09-22 00:03 |只看该作者
更紧密的表


  2. #include <stdio.h>

  4. int myadjust(int shu)
  5. {
  6.     const static unsigned int mytable[]={
  7.       0x75145105, 0x4510414, 0x11411040, 0x45144001, 0x10500504,  
  8.       0x11041401, 0x45001001, 0x14414010, 0x41050450, 0x4001144,  
  9.       0x104014, 0x41010411, 0x4044040, 0x14014110, 0x40451001,  
  10.       0x1101104, 0x500004, 0x10041050, 0x40104141, 0x4500100,  
  11.       0x51041400, 0x44101004, 0x4010104, 0x11010440, 0x44001004,  
  12.       0x500514, 0x1000451, 0x45100, 0x110100, 0x40441040,  
  13.       0x1104101, 0x4004414, 0x1410050, 0x5040001, 0x14410404,  
  14.       0x10400001, 0x40101004, 0x10404004, 0x41050400, 0x40100005,  
  15.       0x10504510, 0x1410000, 0x4104, 0x4000100, 0x40011441,  
  16.       0x1141001, 0x514410, 0x1001010, 0x1044101, 0x10110004,  
  17.       0x41441410, 0x4000041, 0x14000004, 0x50040050, 0x4041041,  
  18.       0x4114, 0x401001, 0x1000100, 0x4114500, 0x40041040,  
  19.       0x140005, 0x410, 0x10450000
  20.     };

  22.    return (mytable[shu >> 5] & ((unsigned int)0x80000000 >> (shu & 0x1F)));

  24. }

  26. int main()
  27. {
  28.    int i;
  29.    for(i=1;i<=2000;i++)
  30.      if(myadjust(i))
  31.        printf("%d is prime number.\n",i);

  33.    return 0;
  34. }

复制代码

[ 本帖最后由 haoji 于 2008-9-22 18:21 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
haoji

论坛徽章:
0
20楼 [报告]
发表于 2008-09-22 00:06 |只看该作者
看来，在百万以内的数字范围，查表法比其他方法效率要高。


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

[ 本帖最后由 haoji 于 2008-9-22 00:12 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP