首页 > 代码库 > c语言输出2~100的素数

c语言输出2~100的素数

这个代码很巧妙,个人的理解都写在了注释里

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//相关的论文:[1]张景龙,黄静,王爱松等.素数判定算法的改进[J].河南科技学院学报(自然科学版),2013,(6):61-64.DOI:10.3969/j.issn.1008-7516.2013.06.015.

//输出100以内的素数,思路:
    //判断素数方法1:
    //假如自然数N不是素数,则除1和其本身之外,必然至少存在两个数A和B,使得A*B=N,
    //则A和B中必有一个大于或者等于sqrt(N),另一个小于或者等于sqrt(N)。下面是粗略证明
    //如果N是合数,则必有一个小于或者等于根号N的素因子.
    //因为任何合数都可表示为两个或者更多个素数之积.
    //假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N.所以合数必有(至少)一个不大于根号N的素因子.
    //n的不大于根号的因子<=sqrt(n);n-1的不大于根号的因子<=sqrt(n-1),显然sqrt(n-1)<sqrt(n);
    //所以2~n内的自然数的因子范围是2~sqrt(n);换句话说2~sqrt(n)的倍数覆盖了了2~n范围内的合数
//数组记录,初始化为0,判断为合数置为1,

#define n 100
int main()
{
    int isPrim[n+1]={0};
    int i,j;

    //判断条件中一定是是i<=sqrt(n)

    //判断素数方法2
    //其中2-sqrt(n)(向下取整)是不是素数该咋判断:
    //根据:判断自然数N是不是合数,就是看2~(N-1)之间有木有数能整除N,换句话说就是2~(N-1)之间有木有数的倍数是N。
    //因为“2-sqrt(n)”中的数若是合数,它的因数肯定是在比自己小的数中产生,
    //由2判断了3是不是合数,由2,3判断了4是不是合数,
    //由2,3,4判断了5是不是合数,依次类推。。。2~(sqrt(n)-1)判断了sqrt(n)是不是合数

    //综合以上下面的这个循环结合了以上两种判断素数的方法,2-sqrt(n)(向下取整)部分用的是方法2结合方法1,
    //(sqrt(n)(向下取整)+1)~n用的是方法1
    for(i=2;i<=sqrt(n);i++){
       if(isPrim[i]==0){
       //这个判断的依据主要是方法2
       //如果不加这个判断,那么还会对4,6,8,10的倍数进行置1,
       //因为这些倍数已经是2的倍数,已经置过1,这进行了重复的工作。
           for(j=2*i;j<=n;j+=i){//这个倍数的循环很好,学习下
                     isPrim[j]=1;
           }
       }
    }
    for(i=2;i<=n;i++){
       if(isPrim[i]==0)
              printf("%d ",i);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//相关的论文:[1]张景龙,黄静,王爱松等.素数判定算法的改进[J].河南科技学院学报(自然科学版),2013,(6):61-64.DOI:10.3969/j.issn.1008-7516.2013.06.015.

//输出100以内的素数,思路:
//判断素数方法1:
//假如自然数N不是素数,则除1和其本身之外,必然至少存在两个数A和B,使得A*B=N,
//则A和B中必有一个大于或者等于sqrt(N),另一个小于或者等于sqrt(N)。下面是粗略证明
//如果N是合数,则必有一个小于或者等于根号N的素因子.
//因为任何合数都可表示为两个或者更多个素数之积.
//假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N.所以合数必有(至少)一个不大于根号N的素因子.
//n的不大于根号的因子<=sqrt(n);n-1的不大于根号的因子<=sqrt(n-1),显然sqrt(n-1)<sqrt(n);
//所以2~n内的自然数的因子范围是2~sqrt(n);换句话说2~sqrt(n)的倍数覆盖了了2~n范围内的合数
//数组记录,初始化为0,判断为合数置为1,

#define n 100
int main()
{
int isPrim[n+1]={0};
int i,j;

//判断条件中一定是是i<=sqrt(n)

//判断素数方法2
//其中2-sqrt(n)(向下取整)是不是素数该咋判断:
//根据:判断自然数N是不是合数,就是看2~(N-1)之间有木有数能整除N,换句话说就是2~(N-1)之间有木有数的倍数是N。
//因为“2-sqrt(n)”中的数若是合数,它的因数肯定是在比自己小的数中产生,
//由2判断了3是不是合数,由2,3判断了4是不是合数,
//由2,3,4判断了5是不是合数,依次类推。。。2~(sqrt(n)-1)判断了sqrt(n)是不是合数

//综合以上下面的这个循环结合了以上两种判断素数的方法,2-sqrt(n)(向下取整)部分用的是方法2结合方法1,
//(sqrt(n)(向下取整)+1)~n用的是方法1
for(i=2;i<=sqrt(n);i++){
if(isPrim[i]==0){
//这个判断的依据主要是方法2
//如果不加这个判断,那么还会对4,6,8,10的倍数进行置1,
//因为这些倍数已经是2的倍数,已经置过1,这进行了重复的工作。
for(j=2*i;j<=n;j+=i){//这个倍数的循环很好,学习下
isPrim[j]=1;
}
}
}
for(i=2;i<=n;i++){
if(isPrim[i]==0)
printf("%d ",i);
}
return 0;
}

c语言输出2~100的素数