筛选求素数和普通求法(C/python略)

2017-11-14 08:11:06来源:CSDN作者:qq_34637408人点击

分享

素数:除了自身之外,无法被其它整数整除的数称之为素数

C代码(普通)

#include<stdio.h>#include<stdlib.h>#include<math.h>#define N 100//普通方法int main(){    int i, j;    for (i = 2; i < N; i++)    {        for (j = 2; j <= sqrt(i); j++)        {            if (i%j == 0)            {                break;            }        }        if (j > sqrt(i))        {            printf("%d/n", i);        }    }    //return 0;    system("pause");}

筛选法

#include<stdio.h>#include<stdlib.h>#include<math.h>#define N 100//筛选求质数//具体筛法是:先把n个自然数按次序排列起来。//1不是质数,也不是合数,要划去。//第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。//2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。//3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。//这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。int main(){    int num=0;    int flag[N+1];    int i, j;    for (i = 2; i <= N; i++)    {        flag[i] = 1;//初始化,表明此时没有数划去    }    for (i = 2; i*i <= N; i++)    {        if (flag[i] == 1)        {            for (j = 2; i*j <= N; j++)            {                flag[i*j] = 0;  //把i的倍数划去            }        }    }    for (i = 0; i <= N; i++)    {        if (flag[i] == 1)        {            printf("%4d", i);            num++;            if (num % 10 == 0)            {                   printf("/n");            }        }    }    printf("/n");    system("pause");}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台