c语言素数筛选法

1. c语言编程:用筛选法求100之内的素数,要求每隔10行输出。怎么写

#include<stdio.h>
#include<math.h>
#include<string.h>
main()
{
int i,j,tem,n;
for(;;)
{
system("cls");
printf("请输入要求素数的上限为：\n");
scanf("%d",&n);
printf("2");
for(i=3;i<=n;i+=2)
{
tem=0;
for(j=2;tem==0&&j<sqrt(i);j++)
if(i%j==0)
tem=1;
if(tem==0)
printf(",%d",i);
}
printf("\n");
system("pause");
}
}
//该素数的求法，比第一种无论是在时间复杂度还是空间复杂度上都要简单的的多
//素数：其实偶数中除了2以外都不是素数，因此只比较奇数即可；当判断一个数是不是素数时，
//往往不必算是否能被2—n-1中任意一个数整除
//只要比较是否能被2—sqrt（n）中的任意个数整除即可！
//当能被其中之一整除时，即能判断该数已不是素数，没有必要再循环判断了！

//============================================================Mr_computer

2. 筛法求素数的C语言实现

1、算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。 #definerange2000boolIsPrime[range+1];//set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEVC++中测试通过voidset(boolIsPrime[]){inti,j;for(i=0;i<=range;++i)IsPrime[i]=true;IsPrime[0]=IsPrime[1]=false;for(i=2;i<=range;++i){if(IsPrime[i]){for(j=2*i;j<=range;j+=i)IsPrime[j]=false;}}}2、
说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=4^2，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。 由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。
因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。 （摘自《C语言名题精选百则（技巧篇）》，冼镜光 编着，机械工业出版社，2005年7月第一版第一次印刷）。代码如下： #include<iostream>#include<cmath>usingnamespacestd;intmain(){intN;cin>>N;int*Location=newint[N+1];for(inti=0;i!=N+1;++i)Location[i]=i;Location[1]=0;//筛除部分intp,q,end;end=sqrt((double)N)+1;for(p=2;p!=end;++p){if(Location[p]){for(q=p;p*q<=N;++q){if(Location[q]){for(intk=p*q;k<=N;k*=p)Location[k]=0;}}}}intm=0;for(inti=1;i!=N+1;++i){if(Location[i]!=0){cout<<Location[i]<<;++m;}if(m%10==0)cout<<endl;}cout<<endl<<m<<endl;return0;}该代码在Visual Studio 2010 环境下测试通过。
以上两种算法在小数据下速度几乎相同。

3. C语言 用筛法求1-1000之间的素数

1、写我们的头文件和主函数。写好我们的开头。

4. C语言编程:用筛选法求100之内的素数,

源代码如下：

#include <stdio.h>

#include <math.h>

int main()

{

int a, b, i, flag;

printf("输入两个整数: ");

scanf("%d %d", &a, &b);

printf("%d与%d之间的素数为: ", a, b);

while(a<b)

{

flag=0;

for(i=2; i<=sqrt(a); i++)

{

if(a%i==0)

{

flag=1;

break;

}

}

if(flag==0)

printf("%d ", a);

a++;

}

return 0;

}

(4)c语言素数筛选法扩展阅读

一个偶数总能表示为两个素数之和的源代码如下：

#include "stdio.h"

#include "math.h"

main()

{

int a,b,c,d;

scanf("%d",&a);

for(b=3;b<=a/2;b+=2)

{

for(c=2;c<=sqrt(b);c++)

if(b%c==0) break;

if(c>sqrt(b))

d=a-b;

else

break;

for(c=2;c<=sqrt(d);c++)

if(d%c==0)

break;

if(c>sqrt(d))

printf("%d=%d+%d ",a,b,d);

}

}

for(int i=5;i<=sqrt(x);i+=6)

if(x%i==0||x%(i+2)==0)

{

printf("%d不是素数",x);

return 0;

}

printf("%d是素数",x);

return 0;

}

5. 解释一下c语言筛选法求素数

如果定义为
a[100]
那么该数组的下标范围是：
a[0]
~
a[99]
为了用
a[100]
就不得不定义到101
这句表示执行以下100行代码：
a[1]=1;
a[2]=2;
a[3]=3;
……
a[100]=100;
用循环语句写就是：
for(i=0;i<101;i++)
a[i]=i;
每当输出到第10个，20个……
90个
的时候就换行
而10，20
……
90
这些数有一个共同特征：
他们
%
10
==0
所以可以这样：
for
(i=1
;
i<101
;
i++)
{
printf("%d
",a[i]);
if
(i%10==0)
printf("\n");
}
*********************************
a[i]不是一个变量
当i分别取1，2，3……，100
的时候
a[i]表示的是a[1],a[2],a[3],……a[100]
这100个变量

6. C语言筛选法判断质数

楼上的别在那误导人，你那叫筛选法吗？
先解释一下筛选法的步骤：
<1>
先将1挖掉(因为1不是素数)。
<2>
用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3>
用3去除它后面的各数，把3的倍数挖掉。
<4>
分别用4、5…各数作为除数去除这些数以后的各数。
上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的N次方的全部置0，3的N次方的全部置0，4的N次方的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了
筛选法程序如下
#include<stdio.h>
int
main()
{
int
x[100001];
int
temp,n,
i;
//初始化数组
for(i=0;i<100001;i++)
x[i]=0;
//初始化数组完成
/*
预计结果，
数组中质数为0，其它为1
*/
x[0]=x[1]=1;//因为
0和1不能通过计算得到，所以只能手工置1
，1即不是合数也不是质数
for(i=2;i<100001;i++)
{//循环数组中的每个数
if(x[i]==0){//如果该数所存的值为0，即第一次接触此数
temp=2*i;//将它的二倍，及n倍（要小于100000）
，都置为1，因为这些数都能被i整除
while(temp<=100000)
{
x[temp]=1;
temp+=i;
}
}
}
scanf("%d",&n);
while(n
!=
0)
{
if(x[n]==0)
printf("素数\n");
else
printf("合数\n");
scanf("%d",&n);
}
return
0;
}
如果你觉得这个方法不好理解，你可以用上面他们写的那些常规算法，但是数字过大的话，算起来是很慢的

7. 用C语言筛选法求100以内的素数

先建立一个数组赋值为2-100

再用二重循环标记每个素数的倍数为0，最后打印出为被标记不为0的数即为素数

#include"stdio.h"

#defineSize99

intmain()

{

inta[Size],i,j;

for(i=0;i<Size;i++)

a[i]=i+2;

for(i=0;i<Size;i++)

{

if(a[i])

{

for(j=i+1;j<Size;j++)

if(a[j]%a[i]==0)

a[j]=0;

}

}

for(i=0;i<Size;i++)

if(a[i]!=0)

printf("%d ",a[i]);

printf(" ");

return0;

}

结果

8. c语言中用筛选法求素数

一个质数。在大于1的自然数中，除1和100整数本身外，不能被任何其他自然数整除的次数。素数在数论中起着重要的作用。

大于1但没有质数通道的数称为合数。1和0既不是质数也不是合数。

通过滤波法得到的100以内质数的源代码如下：

＃include＂stdio．h＂

main（）

main（）

｛

IntI，j。

对于(I = 2;我< 99;我+ +)

｛

对于(j = 2;<我;J + +)

｛

If（I％j＝＝0）

｛

打破；

｝

如果（j＝＝I－1）

｛

Printf（“％4d”，I）；

｝

(8)c语言素数筛选法扩展阅读：

100以内的数字代码如下

包含< bits/stdc++。H >

使用命名空间性病。

Intthesum（Intn）

｛

返回（n／10＋n％10％）＋（10）（n／10％＊（n％10））；

｝

Intmain（）｛

Intn＝100；

For (int I = 10;I < = n;我+ +)

｛

If (sum (I) = = I) cout < < I < < endl;

｝

返回0；

｝

9. 用C语言如何判断素数

素数又称质数，所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1、判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2、判断方法还可以简化。

m 不必被2~m-1之间的每一个整数去除，只需被2~√m之间的每一个整数去除就可以了。如果 m 不能被2~√m间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。

原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。

例如16能被2、4、8整除，16=2*8，2小于 4，8大于4，16=4*4，4=√16，因此只需判定在2~4之间有无因子即可。

两种思路的代码请看解析。

拓展资料：

素数（prime number）又称质数，有无限个。素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

C语言是一门面向过程、抽象化的通用程序设计语言，广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。

网络——C语言