素数判定算法的实现

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的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。

(0)

相关推荐

  • 素数判定算法的实现

    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) {        

  • Python机器学习实战之k-近邻算法的实现

    目录 K-近邻算法概述 工作原理 实施KNN算法 示例:手写识别系统 K-近邻算法概述 简单地说, k-近邻算法采用测量不同特征值之间的距离方法进行分类. k-近邻算法 优点:精度高.对异常值不敏感.无数据输入假定. 缺点: 计算复杂度高.空间复杂度高. 适用数据范围: 数值型和标称型. 工作原理 存在一个样本数据集合, 也称作训练样本集, 并且样本集中每个数据都存在标签, 知道样本集中每一数据与所属分类的对应关系. 输入没有标签的新数据后, 将新数据的每个特征与样本集中数据对应的特征进行比较,

  • php 二维数组快速排序算法的实现代码

    php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递归. 实例代码: <?php class Bubble { private function __construct() { } private static function sortt($data) { if (count ( $data ) <= 1) { return $data; } $tem = $data [0]['sco

  • php仿微信红包分配算法的实现方法

    本文实例讲述了php仿微信红包分配算法的实现方法.分享给大家供大家参考,具体如下: /** * 红包分配:把一定金额随机分配给指定人数 * * @param int $money 用于分配的金额 * @param int $num 分配人数 */ function RandomMoney($money, $num) { echo "$money元随机分成$num份分别是:<br/>"; $remain=$money; $use=0; for ($i=1; $i<$nu

  • Linux内核中红黑树算法的实现详解

    一.简介 平衡二叉树(BalancedBinary Tree或Height-Balanced Tree) 又称AVL树.它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1.0和1.(此段定义来自严蔚敏的<数据结构(C语言版)>) 红黑树 R-B Tree,全称是Red-B

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

  • PHP二分查找算法的实现方法示例

    本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

  • vue2.0中goods选购栏滚动算法的实现代码

    不多说,直接代码,以便以后重复利用: <script type="text/ecmascript-6"> import BScroll from 'better-scroll'; const ERR_OK = 0; export default { props: { sell: { type: Object } }, data() { return { goods: [], listHeight: [], scrollY: 0 }; }, computed: { curre

  • C/C++ MD5算法的实现代码

    在逆向程序的时候,经常会碰到加密的算法的问题,前面分析UC的逆向工程师的面试题2的时候,发现使用了MD5的加密算法(MD5算法是自己实现的,不是使用的算法库函数).尤其是在逆向分析网络协议的时候,一般的程序使用的加密算法都是使用的库函数提供的算法,有些程序使用的算法是自己实现的:相对来说使用函数库提供的加密函数的算法相对来说比较好识别,因为有算法常见函数在:但是如果不是使用的函数库提供的加密的函数而是自己去实现某些算法话,识别起来有一定的难度,这就需要你对函数的加密原理以及流程还算法的特征比较熟

  • 基于ID3决策树算法的实现(Python版)

    实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

随机推荐