java吧 关注:1,250,164贴子:12,734,551
  • 21回复贴,共1

java质数小程序时间比较

只看楼主收藏回复



先来第一个:
public class CountPrimeNumber {
public static void main(String args[]){int count = 0;for(int i = 101; i < 500000; i += 2){if(isPrimeNumber(i)){count++;System.out.print(i + " ");}}System.out.println("\n" + "Total "+ count + " prime number between 101 and 200");}
private static boolean isPrimeNumber(int number) {boolean isPrimeNumber = true;for(int j = 2; j < number; j++){if(number % j == 0){isPrimeNumber = false; }}return isPrimeNumber;}}
坑,09:34.4,约9分钟 求出41513个质数。
第二个:
public class CountPrimeNumber {
public static void main(String args[]){for(int i=100;i<=500000;i++ ){for(int j=2;j<=i;j++){if(i%j==0&&j!=i){break ;}else if(i==j){System.out.println(i);}}}}}
好,01:42.2,不到两分钟。
I


1楼2013-10-08 12:48回复
    = false;之后你再加上个break;
    既然已经确定不是质数了,你还让他循环去验证做什么呢?


    IP属地:山东2楼2013-10-08 12:58
    收起回复
      不过循环到number/2就行了,这样也能节省些时间。


      IP属地:安徽5楼2013-10-08 13:27
      收起回复
        这样应该比你的快一点,思路如下:
        判断一个数是不是质数,只要判断能不能被小于它的平方根的质数整除即可。
        其中的count100是统计的100以前质数的个数。

        I


        IP属地:山东6楼2013-10-08 14:20
        收起回复
          总算是找到正解了



          7楼2013-10-08 15:13
          收起回复
            都不是最快的 筛选法是最快的 但是空间复杂度高


            IP属地:湖北来自Android客户端8楼2013-10-08 15:39
            收起回复
              《编程珠玑•续》第一章有详细讨论。看看吧。你这个……


              IP属地:广东来自手机贴吧9楼2013-10-08 16:38
              回复