打印1到100之间的所有素数及前100个素数的列表
最编程
2024-08-08 21:05:37
...
本来是想第二篇做双链表的,今天看C和指针第四章,复习了以下之前做的素数输出,三种不同方法,结果如下:
1.输出1-100以内的素数:
//这个比较简单,不多做介绍,唯一注意的一点是for循环截止条件是i<sqrt(n),因为对于一个整数n,其是否为素数,在所有小于其平方根的数已经判断完毕,没必要再增加工作量判断到n-1;
#include<stdio.h>
#include<math.h>
int main()
{
int n;
int i;
int flag=0;
for(n=2;n<=100;n++)
{
flag=0;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
flag=1;
break;
}
}
if(flag==0)
printf("%d ",n);
}
return 0;
}
2.同样,也是输出1-100以内的素数,这个构造一个数组,将其所有元素初始化为1,表示素数,这时取x从2开始,到100以内做循环,若x为素数,即prime[x]!=0,使得每个i*x位置元素置0(prime[i*x]=0),表示为非素数,循环结束前x+1。
#include<stdio.h>
int main()
{
int prime[100];
int i;
for(i=0;i<100;i++)
prime[i]=1;
int x=2;
while(x<100) //是每一个数 x*i x=2->100
{
for(i=2;i*x<100;i++)
{
if(prime[x])
{
prime[i*x]=0;
}
}
x++;
}
for(i=2;i<100;i++)
{
if(prime[i])
printf("%d ",i);
}
return 0;
}
3.该方法是输出100个素数,基本思想是构造一个素数表,利用函数判断每个数是否能被其之前的素数整除,如果不能,则在素数表内加上该元素,不断循环(while循环结束条件是cnt即数组个数>100)。
#include<stdio.h>
int isprime(int n,int prime[],int maxnumber);
int main()
{
int prime[100]={2,}; //构造素数表,共100个元素,初始化第一个为2,已知为素数;其余自动为0;
int cnt=1; //计数;
//int count=0;
int i=3; //从3开始;
while(cnt<=100) //cnt是数组现有素数个数
{
if(isprime(i,prime,cnt)) //判断i是否为素数
{
prime[cnt++]=i; //如果是记录到数组中,下标加1;
}
i++; //下一个数
}
for(i=0;i<100;i++)
{
if(i%10==0 && i!=0)
putchar('\n');
printf("%5d",prime[i]);
}
return 0;
}
int isprime(int n,int prime[],int maxnumber)
{
int i;
for(i=0;i<maxnumber;i++)
{
if(n%prime[i]==0) //判断能否被素数表中的数整除,如果能,则不是素数
return 0;
}
return 1;
}
上一篇: c
下一篇: C语言文件操作实战训练(上)