当前位置: 首页 > news >正文

做头像的网站有哪些重庆大渡口网站建设

做头像的网站有哪些,重庆大渡口网站建设,想学做电商怎么加入,百度关键词指数排行From: http://blog.csdn.net/dinosoft/article/details/5829550 素数总是一个比较常涉及到的内容#xff0c;掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数#xff0c;直接枚举因子2 。。N^(0.5) #xff0c;看看能否整除N。 如果需要…From: http://blog.csdn.net/dinosoft/article/details/5829550 素数总是一个比较常涉及到的内容掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数直接枚举因子2 。。N^(0.5) 看看能否整除N。 如果需要判断的次数较多则先用下面介绍的办法预处理。  一般的线性筛法 首先先介绍一般的线性筛法求素数 [cpp] view plaincopyprint? void make_prime()  {            memset(prime, 1, sizeof(prime));      prime[0]false;           prime[1]false;           int N31700;            for (int i2;  iN;  i)                 if (prime[i]) {                    primes[cnt ]i;               for (int ki*i; kN; ki)                      prime[k]false;               }            return;  }      这种方法比较好理解初始时假设全部都是素数当找到一个素数时显然这个素数乘上另外一个数之后都是合数(注意上面的 i*i ,  比 i*2 要快点 )把这些合数都筛掉即算法名字的由来。 但仔细分析能发现这种方法会造成重复筛除合数影响效率。比如10在i2的时候k2*15筛了一次在i5k5*6 的时候又筛了一次。所以也就有了快速线性筛法。   快速线性筛法 快速线性筛法没有冗余不会重复筛除一个数所以“几乎”是线性的虽然从代码上分析时间复杂度并不是O(n)。先上代码 [cpp] view plaincopyprint? #includeiostream   using namespace std;      const long N  200000;     long prime[N]  {0},num_prime  0;      int isNotPrime[N]  {1, 1};     int main()      {               for(long i  2 ; i  N ; i )                 {                      if(! isNotPrime[i])                             prime[num_prime ]i;            //关键处1                   for(long j  0 ; j  num_prime  i * prime[j]   N ; j )              {                                 isNotPrime[i * prime[j]]  1;                if( !(i % prime[j] ) )  //关键处2                                    break;                     }              }              return 0;     }     首先先明确一个条件任何合数都能表示成一系列素数的积。   不管 i 是否是素数都会执行到“关键处1” ①如果 i 都是是素数的话那简单一个大的素数 i 乘以不大于 i 的素数这样筛除的数跟之前的是不会重复的。筛出的数都是 Np1*p2的形式, p1p2之间不相等   ②如果 i 是合数此时 i 可以表示成递增素数相乘 ip1*p2*...*pn, pi都是素数2in  pipj  ( ij ) p1是最小的系数。 根据“关键处2”的定义当p1prime[j] 的时候筛除就终止了也就是说只能筛出不大于p1的质数*i。   我们可以直观地举个例子。i2*3*5 此时能筛除 2*i ,不能筛除 3*i 如果能筛除3*i 的话当 i 等于 i3*3*5 时筛除2*i 就和前面重复了。   需要证明的东西 一个数会不会被重复筛除。合数肯定会被干掉。 根据上面红字的条件现在分析一个数会不会被重复筛除。 设这个数为 xp1*p2*...*pn, pi都是素数1in)  ,  pipj ( ij ) 当 i 2 时就是上面①的情况 当 i 2 时 就是上面②的情况 对于 i 第一个能满足筛除 x 的数  y 必然为 yp2*p3...*pnp2可以与p1相等或不等而且满足条件的 y 有且只有一个。所以不会重复删除。 证明合数肯定会被干掉 用归纳法吧。  类比一个模型比如说我们要找出 n 中2个不同的数的所有组合 { i , j } 1in, 1jn, 我们会这么写 for (i1; in; i )   for (ji1; jn; j)    {     /    } 我们取 ji1 便能保证组合不会重复。快速筛法大概也是这个道理不过这里比较难理解没那么直观。   1楼提供的方法我整理下 //偶数显然不行所以先去掉偶数。可以看作上面第一种的优化吧。 //不过这种方法不太直观不太好理解。   [cpp] view plaincopyprint? 我推荐这个算法 易于理解。 只算奇数部分时空效率都还不错  halfSIZE/2;   int sn  (int) sqrt(SIZE);   for (i  0; i  half; i)      p[i]  true;// 初始化全部奇数为素数。p[0]对应3即p[i]对应2*i3   for (i  0; i  sn; i) {      if(p[i])//如果 ii3 是素数  {           for(kii3, jk*iki; j  half; jk)       // 筛法起点是 p[i]所对应素数的平方 k^2                                              // k^2在 p 中的位置是 k*iki       //    下标 i         k*iki       //对应数值 kii3   k^2                  p[j]false;   }   }   //素数都存放在 p 数组中p[i]true代表 ii2 是素数。  //举例3是素数按3*3,3*5,3*7...的次序筛选因为只保存奇数所以不用删3*43*6....   扩展阅读 打印质数的各种算法 http://coolshell.cn/articles/3738.html  里面有个用C模板实现的纯属开阔眼界不怎么实用。检查素数的正则表达式  http://coolshell.cn/articles/2704.html  数字n用  1111。。1 n个1表示纯属坑爹。 以上完整源码(a.cpp) /* 功能: 求[0, 20000)间的所有素数, 假设内存空间足够 环境: Linux C 编译: g -o a a.cpp -Wall -Os 总结: 这两种算法在性能上差距不是很大, 当N个数较少时, 还是一般线性筛选法速度更快, 但是当N较大时, 快速线性筛选法的优势更加明显 */ #include stdio.h #include string.h #define N 20000 // 一般线性筛选法: 会出现重复筛选同一个数 void make_prime(int primes[], int cnt) { bool bPrime[N]; // 质数标志数组 cnt 0; // 素数个数 memset(bPrime, true, sizeof(bPrime));// 假设全是素数 bPrime[0] false; // 0: 非素数 bPrime[1] false; // 1: 非素数 for (int i 2; i N; i) { if (bPrime[i]) // i是素数 { primes[cnt] i; // 将素数i保存到bPrimes[]中 // 作筛选: i的倍数都不是素数 for (int k i * i; k N; k i) // 将素数i的倍数全置为非素数标志 bPrime[k] false; } } } // 快速线性筛选法: 不会出现重复筛选同一个数 void getPrimes(int primes[], int cnt) { bool bPrime[N]; // 素数标志数组 cnt 0; // 素数个数 memset(bPrime, true, sizeof(bPrime)); // 假设全部为素数 bPrime[0] false; // 0: 非素数 bPrime[1] false; // 1: 非素数 for(int i 2; i N; i) { if(bPrime[i]) // i是素数 primes[cnt] i; // 保存素数i // 作筛选: i与素数的乘积都不是素数 for(int j 0; j cnt i * primes[j] N; j) { bPrime[i * primes[j]] false; // 置非素数标志 if(i % primes[j] 0) // i为素数的倍数 break; } } } int main() { int primes[N]; // 保存所有素数 int cnt 0; // 素数个数 #if 1 make_prime(primes, cnt); // 调用一般线性筛选法 #else getPrimes(primes, cnt); // 调用快速线性筛选法 #endif for(int i 0; i cnt; i) printf(primes[%d] %d\n, i, primes[i]); printf(\n素数个数cnt%d\n, cnt); return 0; }
http://wiki.neutronadmin.com/news/305129/

相关文章:

  • 做虾苗网站有哪些流程学校网站制作平台
  • 网站介绍视频怎么做的怎么修改网页源代码
  • 手机网站建设在哪儿大学校园网站建设
  • 新网站的站点验证有中文网站 怎么做英文网站
  • 哈尔滨免费模板建站顶尖网站设计
  • 电子商务网站建站流程介绍一个地方旅游网站怎么做
  • 个人免费建站系统泰州网页制作
  • 西安网站建设招聘如何策划网络事件营销
  • 库尔勒网站密云建设银行招聘网站
  • 专门做dm单的网站vr软件开发需要学什么
  • 张家口外贸网站建设济宁市工程建设职业学校网站
  • 自动优化网站建设电话wordpress 加文章列表
  • 宁波网站建设首选品牌艺点意创官网
  • 有链接的网站怎么做定制微信小程序多少钱
  • 国外做兼职网站有哪些深圳做网站的网
  • 网站主办单位负责人2019做网站需要营业执照吗
  • 网站建设的栏目策划石家庄招聘求职信息网
  • 淘宝购物网站的建设现在外贸推广做哪个平台
  • 旅游网站源码 wordpress模板 v1.0html语言做的网站和asp的区别
  • 北京网站建设最便宜的公司哪家好兰州建设网站的网站
  • 网站项目根据什么开发百度信息流优化
  • 西安建网站的公司广告设计制作服务方案
  • 有做企业网站的吗运营推广seo招聘
  • 开源 企业网站一元域名注册永久
  • 吴江区建设局网站网站如何做中英文效果
  • 外贸婚纱网站 侵权郑州市建设厅网站
  • 网站设计的书网站建设公司源码
  • 北京大兴网站建设公司咨询php怎样做网站管理后台
  • 制作网站的图片素材做防腐木网站
  • 网站关键词代码怎么做wordpress 代码位置