素数算法(小汇)-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

素数算法(小汇)

简介:

Java算法——判断素数

public static boolean isPrimeNumber(int number){
     if(number<2)
         return false;
     for(int i=2;i<=Math.sqrt(number);i++){
         if(number%i==0&&number!=2)
             return false;
     }
     return true;
 }

素数算法(二)

上次讨论了简单的素数判定的算法,不过这个算法对于位数较大(一般小于108)的素数判定就显得相当力不从心了。比如在素数目前最广泛的应用领域-公共密钥体系中,一般选择的素数都是相当大的(通常在100位以上),如果采用上次的试除法来判定,那么可能要穷尽你一生的时间都还不够。所以在一般的应用领域,人们采用的是Rabin-Miller检验法。下面是该检验法的算法:

首先选择一个代测的随机数p,计算b,b是2整除p-1的次数。然后计算m,使得n=1+(2^b)m。

(1) 选择一个小于p的随机数a。
(2) 设j=0且z=a^m mod p
(3) 如果z=1或z=p-1,那麽p通过测试,可能使素数
(4) 如果j>0且z=1, 那麽p不是素数
(5) 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p,然后回到(4)。如果z=p-1,那麽p通过测试,可能为素数。
(6) 如果j=b 且z<>p-1,不是素数

数a被当成证据的概率为75%。这意味着当迭代次数为t时,它产生一个假的素数所花费的时间不超过1/4^t。实际上,对大多数随机数,几乎99.99%肯定a是证据。

实际考虑:

在实际算法,产生素数是很快的。

(1) 产生一个n-位的随机数p
(2) 设高位和低位为1(设高位是为了保证位数,设低位是为了保证位奇数)
(3) 检查以确保p不能被任何小素数整除:如3,5,7,11等等。有效的方法是测试小于2000的素数。使用字轮方法更快
(4) 对某随机数a运行Rabin-Miller检测,如果p通过,则另外产生一个随机数a,在测试。选取较小的a值,以保证速度。做5次 Rabin-Miller测试如果p在其中失败,从新产生p,再测试。

经测试,这个算法在sun的Sparc II工作站上实现: 
2 .8秒产生一个256位的素数
24.0秒产生一个512位的素数
2分钟产生一个768位的素数
5.1分钟产生一个1024位的素数


最近在网上看了不少关于素数的问题,也学习到了不少东西,决定整理一下,算是一个学习的总结吧。

首先想说明的是,虽然素数可以进行很深入的研究(如在RSA公共密钥系统的应用),但是由于我对数论的不甚熟悉,所以只能做一些浅尝辄止的探讨,主要就是对一些简单的素数相关算法进行一个讨论。

首先来说说素数的判定算法,如果你是读谭浩强老师的《c程序设计》入门的话,那么一谈到素数的判定算法,你首先应该想到的就是以下的算法:给定一个正整数n,用2到sqrt(n)之间的所有整数去除n,如果可以整除,则n不是素数,如果不可以整除,则n就是素数。这个算法的时间复杂度十分明了,为O(sqrt(n)),算法的描述相当简单,实现也一样不困难。

# include <stdio.h>
# include <math.h>

int isPrime(int n)
{
    int i ;
 
    for(i=2; i <= sqrt(n); i++){
        if(n%i == 0 )
            break ;
    }

    if(i <= sqrt(n))
        printf("%d is not a prime ! ", &n) ;
    else
        printf("%d is a prime ! ", &n) ;
 
    return 0 ;
}


=====================================
public class  SuShu{   
 private int num;  
 SuShu(int n){    
  num=n;
 }  
 public  boolean isSuShu(){
  for(int i=2;i<num;i++){
   if(num%i==0)
    return false;                 
  }     
   return true;  
 }  
 public static void main(String[] args){    
  for(int i=1;i<=100;i++){
   SuShu su=new SuShu(i);
   if(su.isSuShu())
    System.out.println(i+"是素数");
   else
    System.out.println(i+"不是素数");    
  } 
 }
}

=============================

/**   
* @param n   
* @return if n is a prime return true, else false   
*/  
public static boolean isPrime(int n) {
 // filte negative, zero, one    
 if (1 >= n) {
       return false;
 }
 // 2 is a prime, stop filter    
 if (2 == n) {
  return true;
 }
 // filter evens 
 if (0 == n % 2) {
  return false;
 }
 // go on filting...    
 for (int a = 3; a <= Math.sqrt(n); a += 2) {
  if (0 == n % a) {
   return false;
  }
 }
 // the rest is all prime, stop filting    
 return true;
}
==============================
//目前我认为最好的办法是:(不是lk的观点)
public boolean isPrime(int n){
    for(int i = 2; i * i <= n; i++){
  if(n % i == 0)
   return false;
  }
    return true;
}
===============================
素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。 
有的数,如果单凭印象去捉摸,是无法确定它到底是不是素数的。有些数则可以马上说出它不是素数。一个数,不管它有多大,只要它的个位数是2、4、5、6、8或0,就不可能是素数。此外,一个数的各位数字之和要是可以被3整除的话,它也不可能是素数。但如果它的个位数是1、3、7或9,而且它的各位数字之和不能被3整除,那么,它就可能是素数(但也可能不是素数)。没有任何现成的公式可以告诉你一个数到底是不是素数。你只能试试看能不能将这 
个数表示为两个比它小的数的乘积。

代码如下:

package com.vo;

public class Sushu {


 public static void main(String[] args) {
  int s=0;
  int i;
  for(i=0;i<=100;i++)
  {
 int j;
 for(j=2;j<=i;j++){
  if(i%j==0)
   break;
 }
 if(i==j)
  System.out.println(i);
  }

 }

}

 本文转自博客园执着的笨蛋的博客,原文链接:素数算法(小汇),如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章