c语⾔之筛法求素数
描述
⽤筛法输出N以内的所有素数。
筛法是求不超过⾃然数N（N>1）的所有素数的⼀种⽅法。据说是古希腊数学家埃拉托斯特尼（约公元前274~194年）发明的，⼜称埃拉托斯特尼筛法。
具体做法是：先把N个⾃然数依次排列起来。1不是素数，也不是合数，要划去。第⼆个数2是素数留下来，⽽把2后⾯所有能被2整除的数划去。2后⾯第⼀个没有划去的数是3，把3留下，再把3后⾯所有能被3整除的数划去。3后⾯第⼀个没有划去的数是5，把5留下，再把5后⾯所有能被5整除的数划去。\cdots…，这样⼀直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部素数。
因为希腊⼈是把数写在涂蜡的板上，每要划去⼀个数，就在上⾯记以⼩点，寻求素数的⼯作完毕后，这许多⼩点就像⼀个筛⼦，所以就把埃拉托斯特尼的⽅法叫做“埃拉托斯特尼筛法”，简称“筛法”。
输⼊
⼀个整数N（1 < N \leq 100001<N≤10000）。
输出
输出满⾜条件的所有素数，相互之间⽤1个空格隔开，⾏⾸⾏末均⽆空格。
输⼊样例 1
20
输出样例 1
2 3 5 7 11 13 17 19
#include <stdio.h>
int f(int a)
{
int i;
for(i=2;i<a;i++)
{
if(a%i==0)
break;
}
if(i>=a)
return 1;
else return 0;
}
int main(int argc,char const *aegv[])
{
int a[10000]={0},n,i,z=1,j=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{  a[i]=z;
z++;
}
i=1;
while(i<n)
{  if(a[i]!=0)
{
j=f(a[i]);
int w;
if(j==1)
for(w=i+1;w<n;w++)
{
if(a[w]%a[i]==0)
{
a[w]=0;
}
}
}
i++;
}
a[0]=0;
int k=0;
for(i=0;i<n;i++)
{
if(a[i]!=0)
{  if(k!=0)
printf(" ");
printf("%d",a[i]);
k++;
}
}
c语言如何去学}
先写个函数判断是否为素数，然后给给数组赋值，判断数组的⾄是否是素数，是素数就留下且它的倍数全赋值为0，a[i]的值如果为0则不能输出且必定不为素数直接排除

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