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);
}
return0;
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>c++判断素数
//相关的论⽂：[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;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。