筛素数C语言
❶ 筛法求素数...c语言...
给你原理，你就应该明白是怎么回事了
求素数n，n是否会被2~n之间的数整除，如果不整除，那么是素数，有一个整除了，就不是素数，这个道理应该明白
那么就是一个游遍2~n这些数，判断是否有整除的
但是2~n所判断的数太多，要缩小范围
一个数的因子是围绕根号n两边排列的，也就是说，在根号n之前有个数x可以整除n，设x*y=n的话，y一定在根号n到n之间，这个道理也不难验证
因为xy大小最接近的时候，是x=y，就是x*x=n的话，x就等于根号n。要是xy不相等的话，一个小于根号n，那么另一个必然大于根号n
所以只判断2~根号n之间的数就可以，也就是判断一半。
1~100之间的数据，那么因子只判断2~10之间的就可以，要是更精简一些，值判断10之前的素数即可，因为8 9 10在2 3 的时候已经为零了
❷ C语言筛法求100以内的素数
#include<stdio.h>
int main()
{
int i,j;//定义两个变量，i是从2到100的数字，j是用来被i除，检验i是否是素数的数
for(i=2;i<=100;i++)//i从2到100，挨个枚举，用下面的算法检验
{
for(j=2;j<i;j++)//j从2到i-1，用i除以j
{
if(i%j==0)//如果i除以j的余数是0，即i不是素数
{
break;//跳出循环
}
if(j==i-1)//如果直到j=i-1时上面的判断一直没成立，即i不是素数，输出i
{
printf("%d ",i);
}
}
}
return 0;
}
这是我能写出来的最简单的算法没用数组，函数什么的，你应该能看懂
打字不易，如满意，望点赞。
❸ C语言 用筛选法求100以内的素数
#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
❹ C语言 用筛法求1-1000之间的素数
1、写我们的头文件和主函数。写好我们的开头。
❺ 筛法求素数，求详解！谢谢。用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 环境下测试通过。
以上两种算法在小数据下速度几乎相同。
❻ c语言编程 素数筛选
用筛法求100以内的素数：
#include<stdio.h>
int main()
{
int a[101],i,j;
for(i=2;i<=100;i++)
a[i]=1;
for(i=2;i<=10;i++)
for(j=i+i;j<=100;j+=i)
a[j]=0;
printf("100以内的素数： ");
for(i=2;i<=100;i++)
if(a[i])printf("%d ",i);
printf(" ");
getch();
return 0;
}
❼ 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）；
｝
(7)筛素数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；
｝
❽ c语言用筛法求之N内的素数.
错误相当的多
#include<stdio.h>
intmain()
{
intn,i,j,k,t,a,b,s[100];//最多只能存100个素数。有说n的最大值吗？如果n最大超过546这里会出错
while(scanf("%d",&n)!=EOF)
{
t=0;
if(n==2)
printf("2 ");
else
{
for(j=2;j<n;j++)
{
b=0;//每次标志b要初始化一下不然判断会出错
for(i=2;i<j;i++)
{
a=j%i;
if(a==0)
{
b=1;
break;
}
}
if(b!=1)
{
s[t]=j;
t++;
}
}
for(k=0;k<t;k++)//k从0到t-1
{
printf("%d ",s[k]);//用%d打印s[k]而不是s[t]
}
}
}
return0;
}
而且怀疑算法用错了。
不知道你们老师告诉的筛法是什么样子的 我的理解应该用素数筛才对
❾ c语言 用筛选法求100以内的素数
表示看不出你的程序有哪处用到了筛法...ms跟枚举没什么区别...
以下为普通的筛专质数法的程序：
#include<iostream>
#include<stdio.h>
const int N=101;
int a[N],b[N];
int main(void)
{
int i,j;
a[0]=a[1]=1;
for(i=2;i<N;i++)if(!属a[i]){
b[++b[0]]=i;
for(j=(N-1)/i;j>=2;j--)a[j*i]=1;
}
for(i=1;i<=b[0];i++){printf("%d ",b[i]);if(i%5==0)printf("\n");}
return 0;
}
❿ c语言素数筛法
Console.WriteLine("请输入一个数：");
int i=int.Parse(Console.ReadLine());
int j;
for (j = 2; j < i; j++)
{
if (i % j == 0)
{
Console.WriteLine("否"); break;
}
else if (j == i - 1)
{
Console.WriteLine("是"); break;
}
}
Console.ReadKey();
这段代码的意思是输入一个数，先判断i对j求余是否为0，不为0在筛选出素数