素数筛模板
❶ 筛法求素数，求详解！谢谢。用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 环境下测试通过。
以上两种算法在小数据下速度几乎相同。
❷ 用筛法找1-100之间的全部素数。应用程序界面如图所示，写出相关的事件代码。
#include <stdio.h>
#include <math.h>
int main()
{
int i=0; int j=0; int k=0;
char prime[101];//101个数，建立对应的标志数组，为char型，prime[0]没有用到
prime[0] = 0; prime[1] = 0;
for(i=2; i<=100 ;i++) {
prime[i]=1;
} // 先假设都是素数
for(i=2; i<=100; i++) {
if(prime[i] == 1) {
for(j=i+i; j<=100; j=j+i) { prime[j] = 0; }
}
}
for(i=2; i<=100; i++) //把筛选出的素数打印出来
{
if (prime[i] == 1) { printf("%d is prime number\n",i);
}
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在筛选出素数
❹ 筛法求素数
void make_prime() {
memset(prime, 1, sizeof(prime));
prime[0]=false;
prime[1]=false;
int N=31700;
for (int i=2; i<N; i++)
if (prime[i]) {
primes[++cnt ]=i;
for (int k=i*i; k<N; k+=i)
prime[k]=false;
}
return;
素数*另一个数都是合数，排掉这个合数，剩下的都是素数
❺ 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;
}
❻ 1000的素数 筛法
#include <stdio.h>
#include <math.h>
main()
{
#define N 100
int i,j,a[N];
for(i=0;i<=N;i++)
a[i]=i+1;
for(i=1;i<sqrt(N);i++)
{
if(a[i])
{
for(j=i+1;j<=N;j++) //应该为 for(j=i+1;j<N;j++)
{
if(a[j])
if(a[j]%a[i]==0)
a[j]=0;
}
}
}
for(i=1;i<N;i++)
if(a[i])
printf("%d\t",a[i]);
}
❼ 计蒜客练习：简单素数筛法
说实话我这道题也弄了半天 实在不理解它说的（让数组元素的值作为筛去与否的标志，比如筛去以后让元素值为1，然后依次输出就可以了）这段话是什么意思
我是这么做的
#include <stdio.h>
int N,A,B,C=1;
int main()
{
scanf("%d",&N);
for(A=1;A<N+1;A++)
{
C=1;
for(B=2;B<A;B++)
{
if(A%B==0)
C=0;
}
if((C==1)&&(A!=1))
printf("%d\n",A);}
return 0;
}
N是输入的数字，A是从1~N之间每个数字，B是从1~A每个数字
❽ 先来一种比较快速的素数筛选法，这是一种非常高效的筛法 #include<stdio.h> #i
#include<stdio.h>
#include<string.h>
#define MAXN 100 //最大处理范围
int flag[MAXN+1];//质数标识，0表示质数
int main()
{
int i,j;
memset(flag,0,sizeof(flag));
//初始化质数标识为0
for(i=2;i<=MAXN;i++)
//从2开始到最大范围，去掉所有数的整倍数
{
if(!flag[i])
//如果i未做标识
for(j=i*i;j<=MAXN;j=j+i)
//对i的整倍数做标识，因为小于i的倍数的数，在小于i的数时处理完毕，所以从i*i开始即可
if(!flag[j])
//将整倍数的数标识为1，不是质数
flag[j]=1;
}
for(i=2;i<=MAXN;i++)
if(!flag[i])
//根据筛选结果输出质数
printf("%d ",i);
printf("\n");
return 0;
}
❾ 筛法求素数
主要问题出在erat_sieve函数的n=n/2;这个语句上了，本来要计算的是200。结果你在这里把n折半，结果就再后面m=sqrt(n);m的取值就不是根号下200而是100结果10以上的素数就没有做为因子用上，所以直接导致121和169没有被清除出来。
你这个方法不是筛法吧，筛法是不用除法了求模运算的。我写个筛法你看看
#include "stdio.h"
#include "math.h"
int main()
{
char prime[10000]={0};
int i,j,n,m;
for(i=3;i<10000;i+=2) prime[i]=1;
prime[2]=1;
printf("输入整数n（1~n）：");
scanf("%d",&n);
m=sqrt(n);
for(i=3;i<m;i++)
{
for(j=i*2;j<n;j+=i)
{
if(prime[j]) prime[j]=0;
}
}
j=0;
for(i=0;i<n;i++)
{
if(prime[i])
{
printf("%3d ",i);
j++;
if(j%10==0) printf("\n");
}
}
printf("\n%3d ",j);
}
❿ C++ 素数判断代码解析 我是刚接触的C++ 超级菜鸟级别的 求高手帮帮我！
这是筛法求素数
第三步是声明vector类的以int类型为模板的对象，可以简单的认为是一个整型数组，（10000，1）的意思是分配一万个单位，都赋初值为1
4-7步为求素数的过程：
从2开始循环，找到一个标记为素数的（一开始默认全是素数），就将它的倍数全部标记为不是素数（内层循环就是干这个的）
筛法求素数如果不懂可以上网查
接下来是输出
第8行打开叫a.txt的文件
第9行从文件中循环读入数字a，直到到达文件结尾（in>>a)，或者数字不在范围内（a>1&&a<10000)
第10行输出数字a是否素数（还记得吗，我们的prime数组是用来标记一个数是不是素数的，如果a是，prime[a]=1，否则，prime[a]=0）