输出质数

Michael-Bern

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

430524tian

#include <stdio.h>
#include <math.h>

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

int main(){
    int i;
    for( i = 100 ; i < 200 ; i ++ ){
        if( Iszishu(i) ){
            printf("%d ",i);
        }
    }
    return 0;
}

醉酒青牛

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

#include <stdio.h>
int main()
{
    int n,flag;      //声明两个变量，n为需要判断是否为质数的数，flag为判断标志。
    int i;              //需要去整除的数，取值从2到n-1。
    for(n=100; n<=200; n++)        //n值取值范围为100到200
    {
        flag=0;            //每次都需要初始化flag，flag为0表明是质数
        for(i=2; i<n; i++)  //i的取值范围为2到n-1
        {
            if(n%i==0)
            {          
               flag=1;    
               break;             //如果能够被整除则将flag置为1，并跳出内循环
            }
        }
        if(flag ==0)
            printf("%d\n",n);    //输出判断出来的质数
    }
    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函数 判断是素数就打印

bool IsPrimer(int num)
{
    assert(num > 1);

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

    return true;
}

int main(void)
{
    for (int i = 100; i <= 200; i++)
        if (IsPrimer(i))
            printf("%d\n", i);

    return 0;
}

醉酒青牛

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

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

#include <stdio.h>

inline bool IsPrimer(int num)
{
        assert(num > 1);

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

        return true;
}


// 判断是否为素数, Win32裸体汇编
__declspec(naked) int IsPrimerNum(int x) 
{
        __asm
        {

                MOV EBX, 2
                MOV EAX, [ESP+4]
                MOV ECX, [ESP+4]
S0:
                CMP [ESP+4], EBX
                JE S2

                XOR EDX, EDX
                DIV EBX
                TEST EDX, EDX
                JZ  S1
                
                INC EBX
                MOV EAX, [ESP+4]
                LOOP S0
S1:
                XOR EAX, EAX
                RET
S2:
                MOV EAX, 1
                RET
        }
}

int main(void)
{
        time_t start = clock();
        for (int i = 100; i <= 2000; i++)
                if (IsPrimer(i))
                        printf("%d\n", i);
        time_t cost1 = clock() - start;

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

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


        return 0;        
}

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

彼岸花316

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

Michael-Bern

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

非常好，感谢你的指导！

Michael-Bern

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

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