鱼C论坛

 找回密码
 立即注册
查看: 4038|回复: 20

[技术交流] 输出质数

[复制链接]
发表于 2015-8-17 11:48:55 | 显示全部楼层 |阅读模式
100鱼币
请问各位,如何用C语言输出 100-200之间的素数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 11:48:56 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <math.h>

  3. int Iszishu(int num){
  4.     int i;
  5.     for(i = 2;i<=sqrt(num);i++){//此处只要判断到它的平方根即可。
  6.         if(num%i==0) break;  //如果有约数,就不会是质数,可以直接跳出。
  7.     }
  8.     if( i > sqrt(num) ) return 1;  //如果在整个过程中都没有跳出,说明没有数能够整除,说明是质数。用1表示。
  9.     return 0;  //不是质数,用0表示。
  10. }

  11. int main(){
  12.     int i;
  13.     for( i = 100 ; i < 200 ; i ++ ){
  14.         if( Iszishu(i) ){
  15.             printf("%d ",i);
  16.         }
  17.     }
  18.     return 0;
  19. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 13:06:57 | 显示全部楼层
本帖最后由 醉酒青牛 于 2015-8-17 13:36 编辑

首先明白质数的含义,指在一个大于1的自然数中,除了1和自身外,没法被其他自然数整除的数。
因此为了判断100-200之间的质数并输出,需要两个循环,第一个循环控制需要判断的数(100-200),第二个循环用于判定这个数是否为质数,让这个数分别从对2到比这个数小1的数整除,如果循环期间被整除则确定出不是质数,否则判定为质数并打印。具体代码如下:

  1. #include <stdio.h>
  2. int main()
  3. {
  4.     int n,flag;      //声明两个变量,n为需要判断是否为质数的数,flag为判断标志。
  5.     int i;              //需要去整除的数,取值从2到n-1。
  6.     for(n=100; n<=200; n++)        //n值取值范围为100到200
  7.     {
  8.         flag=0;            //每次都需要初始化flag,flag为0表明是质数
  9.         for(i=2; i<n; i++)  //i的取值范围为2到n-1
  10.         {
  11.             if(n%i==0)
  12.             {         
  13.                flag=1;   
  14.                break;             //如果能够被整除则将flag置为1,并跳出内循环
  15.             }
  16.         }
  17.         if(flag ==0)
  18.             printf("%d\n",n);    //输出判断出来的质数
  19.     }
  20.     return 0;
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +2 收起 理由
Michael-Bern + 5 + 5 + 2

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 13:35:51 | 显示全部楼层
楼主,如果觉得回答满意的话一定要把金币赏给俺啊,看在俺这么尽心详细的回答问题的份儿上:handshake

评分

参与人数 1荣誉 +5 贡献 +2 收起 理由
Michael-Bern + 5 + 2

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 13:35:54 | 显示全部楼层
#include <stdio.h>
int main()
{
    int n,flag;      //声明两个变量,n为需要判断是否为质数的数,flag为判断标志。
    int i;              //需要去除的数,取值从2到n-1。
    for(n=100; n<=200; n++)
    {
        flag=0;            //每次都需要初始化flag,flag为0表明是质数
        for(i=2; i<10; i++)  //i的取值范围为2到9就可以判断出是不是能够被别的数整除了
        {
            if(n%i==0){         
               flag=1;   
               break;             //如果能够被整除则将flag置为1,并跳出循环
        }
        if(flag ==0)
            printf("%d\n",n);    //输出判断出来的质数
    }
    return 0;

评分

参与人数 1鱼币 -3 收起 理由
freeparty -3 复制内容

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 13:37:15 | 显示全部楼层
本帖最后由 ryxcaixia 于 2015-8-17 13:39 编辑

顶楼上
我这里随便写个 封装成个bool函数 判断是素数就打印
  1. bool IsPrimer(int num)
  2. {
  3.     assert(num > 1);

  4.     for (int i = 2; i != num; i++)
  5.         if (num % i == 0)
  6.             return false;

  7.     return true;
  8. }

  9. int main(void)
  10. {
  11.     for (int i = 100; i <= 200; i++)
  12.         if (IsPrimer(i))
  13.             printf("%d\n", i);

  14.     return 0;
  15. }
复制代码

评分

参与人数 1鱼币 +5 贡献 +3 收起 理由
Michael-Bern + 5 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 14:35:13 | 显示全部楼层
yjip267 发表于 2015-8-17 13:35
#include
int main()
{

干嘛复制我的帖子内容啊:sweat:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 14:37:59 | 显示全部楼层
ryxcaixia 发表于 2015-8-17 13:37
顶楼上
我这里随便写个 封装成个bool函数 判断是素数就打印

版主大大v5,竟然将判断质数包装成函数进行调用啦。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 16:49:25 | 显示全部楼层
你们不觉得,只判断1-9就行了撒,为什么还要跑到i,这样浪费时间。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 17:16:25 | 显示全部楼层
yjip267 发表于 2015-8-17 16:49
你们不觉得,只判断1-9就行了撒,为什么还要跑到i,这样浪费时间。

是判断到1-9就可以啦,不过我觉得作为初步学习,还是先写好理解的,再写高效的代码,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 21:38:00 | 显示全部楼层
本帖最后由 ryxcaixia 于 2015-8-17 22:57 编辑
yjip267 发表于 2015-8-17 16:49
你们不觉得,只判断1-9就行了撒,为什么还要跑到i,这样浪费时间。


亲  真的会跑到i么
举个例子 100 或者 1000 甚至1w
没等跑到i 跑到2就直接判断为非素数

亲 你考虑下121(11*11) 169(13*13)
并且嗯, 最小的除数是2, 0就不说了 直接溢出了, 1的话素数的定义就直接排除了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-17 22:19:53 | 显示全部楼层
yjip267 发表于 2015-8-17 16:49
你们不觉得,只判断1-9就行了撒,为什么还要跑到i,这样浪费时间。

说说看,1~9怎么就行了?我是新手。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 07:47:45 | 显示全部楼层
开玩笑,1—9肯定是不行的,11,13,17 的倍数怎么鉴别
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 08:40:27 | 显示全部楼层
2-9闭区间。为什么不行呢?11,13,17对2-9的数取余数不等于了0,说明是质数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 08:42:25 | 显示全部楼层
其它的数肯定是2-9的倍数,如果不是2-9的倍数。那就是只有1和本身了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 08:47:45 | 显示全部楼层
哎。没想清楚。对不起了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 10:23:56 | 显示全部楼层
本帖最后由 ryxcaixia 于 2015-8-18 10:29 编辑

心血来潮 不说话 直接上代码
楼主如果是交作业 把这个交上去吧 绝对是提升逼格的利器
  1. #include <stdio.h>

  2. inline bool IsPrimer(int num)
  3. {
  4.         assert(num > 1);

  5.         for (int i = 2; i != num; i++)
  6.                 if (num % i == 0)
  7.                         return false;

  8.         return true;
  9. }


  10. // 判断是否为素数, Win32裸体汇编
  11. __declspec(naked) int IsPrimerNum(int x)
  12. {
  13.         __asm
  14.         {

  15.                 MOV EBX, 2
  16.                 MOV EAX, [ESP+4]
  17.                 MOV ECX, [ESP+4]
  18. S0:
  19.                 CMP [ESP+4], EBX
  20.                 JE S2

  21.                 XOR EDX, EDX
  22.                 DIV EBX
  23.                 TEST EDX, EDX
  24.                 JZ  S1
  25.                
  26.                 INC EBX
  27.                 MOV EAX, [ESP+4]
  28.                 LOOP S0
  29. S1:
  30.                 XOR EAX, EAX
  31.                 RET
  32. S2:
  33.                 MOV EAX, 1
  34.                 RET
  35.         }
  36. }

  37. int main(void)
  38. {
  39.         time_t start = clock();
  40.         for (int i = 100; i <= 2000; i++)
  41.                 if (IsPrimer(i))
  42.                         printf("%d\n", i);
  43.         time_t cost1 = clock() - start;

  44.         start = clock();
  45.         for (int i = 100; i != 2000; i++)
  46.                 if (IsPrimerNum(i))
  47.                         printf("%d\n", i);
  48.         time_t cost2 = clock() - start;

  49.         printf("cost1 = %d\n", cost1);
  50.         printf("cost2 = %d\n", cost2);


  51.         return 0;       
  52. }
复制代码


速度提升个7 8倍不是问题
1.png

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
Michael-Bern + 5 + 5 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-18 10:56:49 | 显示全部楼层
晕,网上随便搜一下,一大堆
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-19 10:03:36 | 显示全部楼层

非常好,感谢你的指导!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-19 10:10:40 | 显示全部楼层
醉酒青牛 发表于 2015-8-17 13:06
首先明白质数的含义,指在一个大于1的自然数中,除了1和自身外,没法被其他自然数整除的数。
因此为了判断10 ...

判断质数的标准
1:不能被任何除1以外的数整除-----做到
2:不能是平方数-----未做到
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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