输出质数

Michael-Bern

请问各位，如何用C语言输出 100-200之间的素数。

430524tian

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int Iszishu(int num){
   
5.     int i;
   
6.     for(i = 2;i<=sqrt(num);i++){//此处只要判断到它的平方根即可。
   
7.         if(num%i==0) break;  //如果有约数，就不会是质数，可以直接跳出。
   
8.     }
   
9.     if( i > sqrt(num) ) return 1;  //如果在整个过程中都没有跳出，说明没有数能够整除，说明是质数。用1表示。
   
10.     return 0;  //不是质数，用0表示。
    
11. }
    
12. 
    
13. int main(){
    
14.     int i;
    
15.     for( i = 100 ; i < 200 ; i ++ ){
    
16.         if( Iszishu(i) ){
    
17.             printf("%d ",i);
    
18.         }
    
19.     }
    
20.     return 0;
    
21. }
    

复制代码

醉酒青牛

首先明白质数的含义，指在一个大于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;

复制代码

醉酒青牛

楼主，如果觉得回答满意的话一定要把金币赏给俺啊，看在俺这么尽心详细的回答问题的份儿上:handshake

yjip267

#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;

ryxcaixia

顶楼上
我这里随便写个 封装成个bool函数 判断是素数就打印

1. bool IsPrimer(int num)
   
2. {
   
3.     assert(num > 1);
   
4. 
   
5.     for (int i = 2; i != num; i++)
   
6.         if (num % i == 0)
   
7.             return false;
   
8. 
   
9.     return true;
   
10. }
    
11. 
    
12. int main(void)
    
13. {
    
14.     for (int i = 100; i <= 200; i++)
    
15.         if (IsPrimer(i))
    
16.             printf("%d\n", i);
    
17. 
    
18.     return 0;
    
19. }

复制代码

醉酒青牛

yjip267 发表于 2015-8-17 13:35
#include
int main()
{

干嘛复制我的帖子内容啊:sweat:

醉酒青牛

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

版主大大v5，竟然将判断质数包装成函数进行调用啦。

yjip267

你们不觉得，只判断1-9就行了撒，为什么还要跑到i,这样浪费时间。

醉酒青牛

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

是判断到1-9就可以啦，不过我觉得作为初步学习，还是先写好理解的，再写高效的代码，

ryxcaixia

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

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

亲 你考虑下121(11*11) 169(13*13)
并且嗯, 最小的除数是2, 0就不说了 直接溢出了, 1的话素数的定义就直接排除了

桃花飞舞

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

说说看,1~9怎么就行了？我是新手。

剑侠

开玩笑，1—9肯定是不行的，11,13,17 的倍数怎么鉴别

yjip267

2-9闭区间。为什么不行呢？11,13,17对2-9的数取余数不等于了0，说明是质数。

yjip267

其它的数肯定是2-9的倍数，如果不是2-9的倍数。那就是只有1和本身了。

yjip267

哎。没想清楚。对不起了。

ryxcaixia

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

1. #include <stdio.h>
   
2. 
   
3. inline bool IsPrimer(int num)
   
4. {
   
5.         assert(num > 1);
   
6. 
   
7.         for (int i = 2; i != num; i++)
   
8.                 if (num % i == 0)
   
9.                         return false;
   
10. 
    
11.         return true;
    
12. }
    
13. 
    
14. 
    
15. // 判断是否为素数, Win32裸体汇编
    
16. __declspec(naked) int IsPrimerNum(int x)
    
17. {
    
18.         __asm
    
19.         {
    
20. 
    
21.                 MOV EBX, 2
    
22.                 MOV EAX, [ESP+4]
    
23.                 MOV ECX, [ESP+4]
    
24. S0:
    
25.                 CMP [ESP+4], EBX
    
26.                 JE S2
    
27. 
    
28.                 XOR EDX, EDX
    
29.                 DIV EBX
    
30.                 TEST EDX, EDX
    
31.                 JZ  S1
    
32.                
    
33.                 INC EBX
    
34.                 MOV EAX, [ESP+4]
    
35.                 LOOP S0
    
36. S1:
    
37.                 XOR EAX, EAX
    
38.                 RET
    
39. S2:
    
40.                 MOV EAX, 1
    
41.                 RET
    
42.         }
    
43. }
    
44. 
    
45. int main(void)
    
46. {
    
47.         time_t start = clock();
    
48.         for (int i = 100; i <= 2000; i++)
    
49.                 if (IsPrimer(i))
    
50.                         printf("%d\n", i);
    
51.         time_t cost1 = clock() - start;
    
52. 
    
53.         start = clock();
    
54.         for (int i = 100; i != 2000; i++)
    
55.                 if (IsPrimerNum(i))
    
56.                         printf("%d\n", i);
    
57.         time_t cost2 = clock() - start;
    
58. 
    
59.         printf("cost1 = %d\n", cost1);
    
60.         printf("cost2 = %d\n", cost2);
    
61. 
    
62. 
    
63.         return 0;       
    
64. }

复制代码

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

彼岸花316

晕，网上随便搜一下，一大堆

Michael-Bern

430524tian 发表于 2015-8-17 11:48

非常好，感谢你的指导！

Michael-Bern

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

判断质数的标准
1：不能被任何除1以外的数整除-----做到
2：不能是平方数-----未做到