Liny_@NotePad

沉迷ACG中

BigInteger 判断素数。。

YOYO posted @ 2009年10月21日 18:16 in 【Java SE】 with tags 高精度 素数判断 , 3541 阅读

又是在问问上看到。。这次的题目是：

编写一个程序，用一个线程显示时间，一个线程用来计算（如判断一个大数是否是质数），当质数计算完毕后，停止显示时间。

于是先用BigInteger的isProbablePrime判断是否可能是素数，然后再进行精确计算（就是从2到sqrt(n) 囧），copy了别人的一个BigInteger sqrt函数~

  1. import java.text.SimpleDateFormat;
  2. import java.math.BigInteger;
  3. import java.util.Date;
  4.  
  5. public class Main
  6. {
  7.         public static void main(String[] args)
  8.         {
  9.                 TimeThread tThread = new TimeThread();
  10.                 BigInteger n = new BigInteger("19890301");
  11.                 CountThread cThread = new CountThread(n, tThread);
  12.                
  13.                 cThread.start();
  14.         }
  15. }
  16.  
  17. class CountThread extends Thread
  18. {
  19.         private SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss.SSS");
  20.  
  21.         private BigInteger number;
  22.         private TimeThread thread;
  23.  
  24.         public CountThread(BigInteger number, TimeThread thread) {
  25.                 this.thread = thread;
  26.                 this.number = number;
  27.         }
  28.  
  29.         public static BigInteger sqrt(BigInteger a) {
  30.                 BigInteger l = BigInteger.ONE;
  31.                 BigInteger h = a;
  32.                 while (l.compareTo(h)<0) {
  33.                         BigInteger m = l.add(h).divide(BigInteger.valueOf(2));
  34.                         int tmp = m.pow(2).compareTo(a);
  35.                         if (tmp == 0) {
  36.                                 return m;
  37.                         }
  38.                         if (tmp < 0) l = m.add(BigInteger.ONE);
  39.                         else
  40.                                 h = m.subtract(BigInteger.ONE);
  41.                 }
  42.                 return l;
  43.     }
  44.  
  45.         public void run() {
  46.                 BigInteger i = new BigInteger("2");
  47.                 BigInteger e = sqrt(number);
  48.                 thread.start();
  49.                 if(number.isProbablePrime(5)) {
  50.                         //      如果这个数有95%的概率是质数 再进行精确判断
  51.                         for(; i.compareTo(e) <= 0; i.add(BigInteger.ONE))
  52.                         {
  53.                                         if(number.mod(i).equals(BigInteger.ZERO)) {
  54.                                                 break;
  55.                                         }
  56.                         }
  57.                 }
  58.                 thread.stopflag();
  59.                 System.out.println("[Result] " + number + " is " + (i.compareTo(e) <= 0 ? "not ":"") + "a prime !");
  60.                 System.out.println("Time start in " + format.format(thread.getStartTime()) + ", end in " + format.format(thread.getEndTime()) + ".");
  61.         }
  62. }
  63.  
  64. class TimeThread extends Thread
  65. {
  66.         private SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss.SSS");
  67.  
  68.         private boolean runFlag = true;
  69.  
  70.         private Date startDate;
  71.  
  72.         private Date endDate;
  73.  
  74.         public void start() {
  75.                 startDate = new Date();
  76.                 super.start();
  77.         }
  78.  
  79.         public Date getStartTime() {
  80.                 return startDate;
  81.         }
  82.  
  83.         public Date getEndTime() {
  84.                 return endDate;
  85.         }
  86.  
  87.         public void stopflag() {
  88.                 runFlag = false;
  89.                 endDate = new Date();
  90.         }
  91.  
  92.         public void run() {
  93.                 while(runFlag) {
  94.                         System.out.println(format.format(new Date()));
  95.                 }
  96.         }
  97. }
 运行截图：

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter