素数判定算法的实现_C 语言

1. 素数判定问题

素数判定问题是一个非常常见的问题,本文介绍了常用的几种判定方法。

2. 原始算法

素数的定义是,除了能被1和它本身整除而不能被其他任何数整除的数。根据素数定义 只需要用2到n-1去除n,如果都除不尽,则n是素数,否则,只要其中有一个数能整除则n不是素数。

复制代码 代码如下:

bool is_primer1(int num) {
 
  int i;
 
  for(i = 2; i < num; i++) {
 
    if(num % i == 0) {
 
      return true;
 
    }
 
  }
 
  return false;
 
}

3. 改进算法

n不是素数,则n可表示为a*b,其中2<=a<=b<=n-1,则a,b中必有一个数满足:1<x<=sqrt(n),因而,只需要用2~sqrt(n)去除n,这样就得到一个复杂度为O(sqrt(n))的算法

复制代码 代码如下:

bool is_primer2(int num) {
 
  int i;
 
  int upper = sqrt(num);
 
  printf("primer2:%d\n", upper);
 
  for(i = 2; i <= upper; i++) {
 
    if(num % i == 0) {
 
      return true;
 
    }
 
  }
 
  return false;
 
}

4. 筛选算法

更高效地素数判断方法应该是将素数预先保存到一个素数表中,当判断一个数是否为素数时,直接查表即可。这种方法需要解决两个问题:

(1) 怎样快速得到素数表?(采用筛选方法)
(2) 怎样减少素数表的大小?(采用位图数据结构)

对于1到n全部整数,逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。具体方法是:

<1> 定义is_primer[i] = true;
<2> 从2开始,依次遍历整个is_primer(直到sqrt(N)),如果is_primer[i]=true,则is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10,则
从2开始遍历:
is_primer[2]=true,则is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true
is_primer[3]=true,则is_primer[6]= is_primer[9]= true
为了减少内存使用率,算法使用了位图数据结构,关于位图,可参考:http://www.jb51.net/article/54439.htm

复制代码 代码如下:

bool load_primer_table1() { //保存素数表
 
  int i;
 
  for(i = 1; i < INT_MAX; i++) {
 
    if(i % 2 != 0 //偶数一定不是素数
 
      && is_primer2(i)) {
 
      set(i);
 
    }
 
  }
 
}
 
bool load_primer_table2() {//另一种更快的方法保存素数表
 
  int i, j;
 
  for(i = 1; i <= INT_MAX; i++) {
 
    if( i % 2) {
 
      set(i);
 
    } else {
 
      clear(i);
 
    }
 
  }
 
  int upper = sqrt(INT_MAX);
 
  for(i = 1; i <= upper; i++) {
 
    if(test(i)) {
 
      for(j = i + i; j < INT_MAX; j += i)
 
        set(i);
 
    }
 
  }
 
}
 
bool is_primer3(long num) { //查表判断是否为素数
 
  if(test(num))
 
    return true;
 
  return false;
 
}

5. 优化的筛选算法

(1) 存储方式优化

仍然采用位图方式存储,只不过是位图中只存储奇数,这样一下子节省了一半空间(需要的空间仅为4G/(32*2)=64MB)
存储空间优化后,算法效率也会提升很多,如:1,2,…,30
只需存储3,5,7,9,11,13,15,17,19,21,23,25,27,29
i=0, is_primer[0] =true, 把下标[3][6][9][12],即9,15,21,27,标为false
i=1, s_primer[0] =true,把下标为[6][11],即15,25标为false
i=2, 2*i+3>sqrt(30),结束
即:i=s, 把下标为s(2*t+1)+3t,其中,t=1,2,3,…中所有的的is_primer置为false

(2) 优化删选算法

a是素数,则下一个起点是a*a,把后面的所有的a*a+2*i*a筛掉。即欲求n以内的素数,就先把sqrt(n)内的素数求出来,用已经求得的素数来筛出后面的合数。

6. 总结

至今为止,没有任何人发现素数的分布规律,也没有人能用一个公式计算出所有的素数。关于素数的很多的有趣的性质或者科学家的努力,如:

(1) 高斯猜测,n以内的素数个数大约与n/ln(n)相当,或者说,当n很大时,两者数量级相同。这就是著名的素数定理。

(2) 十七世纪费马猜测,2的2^n次方+1,n=0,1,2…时是素数,这样的数叫费马素数,可惜当n=5时,2^32+1就不是素数,至今也没有找到第六个费马素数。

(3) 18世纪发现的最大素数是2^31-1,19世纪发现的最大素数是2^127-1,20世纪末人类已知的最大素数是2^859433-1,用十进制表示,这是一个258715位的数字。

(4) 孪生素数猜想:差为2的素数有无穷多对。目前知道的最大的孪生素数是1159142985×2^2304-1和1159142985×2^2304+1。

(5) 歌德巴赫猜想:大于2的所有偶数均是两个素数的和,大于5的所有奇数均是三个素数之和。其中第二个猜想是第一个的自然推论,因此歌德巴赫猜想又被称为1+1问题。我国数学家陈景润证明了1+2,即所有大于2的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。

时间: 2024-09-19 08:52:59

素数判定算法的实现_C 语言的相关文章

C程序实现整数的素数和分解问题_C 语言

本文以实例形式讲述了C程序实现整数的素数和分解问题,分享给大家供大家参考之用.具体方法如下: 要求:对于一个给定的整数,输出所有这种素数的和分解式,对于同构的分解只输出一次(比如5只有一个分解2+3,而3+2是2+3的同构分解式). 例如: 对于整数8,可以作为如下三种分解: (1) 8 = 2 + 2 + 2 + 2 (2) 8 = 2 + 3 + 3 (3) 8 = 3 + 5   看到此题时,我的头一反应是求解背包问题 思路如下: f(N, array) = f(N - array[i],

C语言之字符串模糊查询方法的实现_C 语言

字符串模糊查询,主要是输入不完全的信息进行查找,即每次查找的是待查询的内容中是否含有输入的内容,如果有,则表示找到了.下面详细的介绍下模糊查询的实现方法,代码如下: #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, const char * argv[]) { char str[] = "hello welcome to china\0"; //

解析C++浮点数无效值的定义与无效值判定的小结_C 语言

在实际计算中可能会出现浮点型的无效数据,格式化输出到文件中内容为1.79769e+308,输出到界面就是很大一串数据.这两种方式无论哪种在阅读和查找时就不是很方便.在开发中遇见浮点型数据无效值得判定. 无效值定义如下:#define InvalidDouble *(double*)("\xff\xff\xff\xff\xff\xff\xef\x7f")double  price;.........(计算步骤省掉)price=GetPrice(); //获取数据 通过下面方式对浮点型的无

排列和组合算法的实现方法_C语言经典案例_C 语言

排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现. 本人在经过多次摸索和思考之后,总结如下,以供参考. 程序代码如下: #include <stdio.h> #include <stdlib.h> char array[] = "abcd"; #define N 4 #define M 3 int queue[N] = {0}; int top = 0; int flag[N] = {0}; void perm(int s, int n) { i

c语言-杭电oj2012素数判定 可以运行为什么通不过

问题描述 杭电oj2012素数判定 可以运行为什么通不过 #include "stdio.h" int main() { int x,y,n,j,s; while( scanf("%d%d",&x,&y)!=EOF) { if( x==0 && y==0 ) break; else { for( n=x; n<=y; n++ ) { s=n*n+n+41; for( j=2; j<=s/2; j++ ) { if( s%j

C++变位词问题分析_C 语言

在<编程珠玑>一书的第二章提到了一个变位词问题,变位词指的是一个单词可以通过改变其他单词中字母的顺序来得到,也叫做兄弟单词,如army->mary.由变位词可以引申出几个算法问题,包括字符串包含问题,比较两个字符串是否是变位词,以及找出字典中变位词集合的问题. 一.字符串包含问题 (1) 问题描述:存在字符串1和字符串2,假设字符串2相对较短,如何快速地判定字符串2中的字符都存在于字符串1里(假定字符串只包含字母)? (2) 举例:字符串1为ABCDEFGHIJK,字符串2为ABCDE,

STL list链表的用法详细解析_C 语言

本文以List容器为例子,介绍了STL的基本内容,从容器到迭代器,再到普通函数,而且例子丰富,通俗易懂.不失为STL的入门文章,新手不容错过! 0 前言1 定义一个list2 使用list的成员函数push_back和push_front插入一个元素到list中3 list的成员函数empty()4 用for循环来处理list中的元素5 用STL的通用算法for_each来处理list中的元素6 用STL的通用算法count_if()来统计list中的元素个数7 使用count_if()的一个更

HDU 2012 素数判定

素数判定 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 67408    Accepted Submission(s): 23380 Problem Description 对于表达式n^2+n+41,当n在(x,y)范围内取整数值时(包括x,y)(-39<=x<y<=50),判定该表达式的值是否都为素数.   Input 输

最小生成树算法之Prim算法_C 语言

本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中