看流星社区

 找回密码
 注册账号
查看: 1930|回复: 0

[算法练习]找出40000以内的素数

[复制链接]

该用户从未签到

发表于 2017-6-1 13:33:01 | 显示全部楼层 |阅读模式
使用筛法
比如2是素数,那么2的倍数都不是素数,下一个是3 是素数,3的倍数都不是素数,下一个是5(4在前已经被排除了).....
  1. #include <stdio.h>
  2. #define MAXN 40000
  3. int SPrime(void)
  4. {
  5.         int i = 0;
  6.         int j = 0;
  7.         int prinme[MAXN] = {0};
  8.         int n = 0;
  9.         for (i = 2; i < MAXN; i++)
  10.         {
  11.                 prinme[i] = 1;
  12.         }
  13.         for (i = 2; i < MAXN; i++)
  14.         {
  15.                 if(prinme[i] == 1)
  16.                 {
  17.                         for (j = 2; i*j < MAXN; j++)//倍数置0
  18.                         {
  19.                                 prinme[i*j] = 0;
  20.                         }
  21.                 }
  22.         }
  23.         freopen("output.txt", "w", stdout);
  24. <span style="white-space:pre">        </span>//最后数组中为1的就是素数
  25.         for (i = 0 ,j = 0; j < MAXN; j++)
  26.         {
  27.                 if(prinme[j] == 1)
  28.         {
  29.                         printf("%d ",j);
  30.                         n++;
  31.                         if(n == 13)
  32.                         {
  33.                                 n = 0;
  34.                                 printf("\n");
  35.                         }
  36.                         i++;
  37.                 }
  38.         }
  39.         return i;
  40. }
  41. void main()
  42. {
  43.         int num = SPrime();
  44.         printf("\n素数个数:%d\n",num);
  45.         freopen( "CON", "w", stdout );
  46.         printf("素数个数:%d\n具体数据见运行目录output.txt\n",num);
  47.         getchar();
  48. }
复制代码
点击按钮快速添加回复内容: 支持 高兴 激动 给力 加油 苦寻 生气 回帖 路过 感恩
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

小黑屋|手机版|Archiver|看流星社区 |网站地图

GMT+8, 2024-3-19 16:35

Powered by Kanliuxing X3.4

© 2010-2019 kanliuxing.com

快速回复 返回顶部 返回列表