快捷導(dǎo)航

Java實(shí)現(xiàn)求小于n的質(zhì)數(shù)的3種方法

更新時(shí)間：2015年03月28日 09:54:40 投稿：junjie

這篇文章主要介紹了Java實(shí)現(xiàn)求小于n的質(zhì)數(shù)的3種方法,本文給出了根據(jù)定義去求解、平方根、找規(guī)律三種解法,需要的朋友可以參考下

質(zhì)數(shù)概念

質(zhì)數(shù)，又稱素?cái)?shù)，指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，無(wú)法被其他自然數(shù)整除的數(shù)（也可定義為只有1和本身兩個(gè)因數(shù)的數(shù)）。
最小的素?cái)?shù)是2，也是素?cái)?shù)中唯一的偶數(shù)；其他素?cái)?shù)都是奇數(shù)。質(zhì)數(shù)有無(wú)限多個(gè)，所以不存在最大的質(zhì)數(shù)。

一：根據(jù)定義去求解：
也是最笨的方式，效率比較低：

package test.ms;

public class FindPrime {
	 // find the prime  between 1 to 1000;
	public static void main(String[] args) {
		 printPrime(1000);
	}
	public static void  printPrime(int n){
		
		for(int i = 2; i < n ; i++){
			
			int count = 0;
			
			for(int j = 2 ; j<=i; j++){
				
				if(i%j==0){
					count++;
				}
				if(j==i & count == 1){
					System.out.print(i+" ");
				}
				if(count > 1){
					break;
				}
			}
			
			
		}
		
	}

}

2：平方根：

package test.ms;

public class Prime { 
	
	public static void main(String[] args) {
		
		for(int j = 2; j<1000; j++){
			if(m(j)){
				System.out.print(j+" ");
			}
		}
	}
	
	public static boolean  m(int num){
	
		for(int j = 2; j<=Math.sqrt(num);j++){
			if(num%j == 0){
				return false;
			}
		}
		
		return true;
	}

}

3：找規(guī)律（摘自一個(gè)論壇討論）

最小的素?cái)?shù)是2，也是素?cái)?shù)中唯一的偶數(shù)；其他素?cái)?shù)都是奇數(shù)。質(zhì)數(shù)有無(wú)限多個(gè)，所以不存在最大的質(zhì)數(shù)。

package test.ms;

import java.util.ArrayList;
import java.util.List;

public class Primes {
		 
	  public static void main(String[] args) {
	  	
	    // 求素?cái)?shù)
	    List<Integer> primes = getPrimes(1000);
	 
	    // 輸出結(jié)果
	    for (int i = 0; i < primes.size(); i++) {
	      Integer prime = primes.get(i);
	      System.out.printf("%8d", prime);
	      if (i % 10 == 9) {
	        System.out.println();
	      }
	    }
	  }
	 
	  /**
	   * 求 n 以內(nèi)的所有素?cái)?shù)
	   *
	   * @param n 范圍
	   *
	   * @return n 以內(nèi)的所有素?cái)?shù)
	   */
	  private static List<Integer> getPrimes(int n) {
	    List<Integer> result = new ArrayList<Integer>();
	    result.add(2);
	 
	    for (int i = 3; i <= n; i += 2) {
	      if (!divisible(i, result)) {
	        result.add(i);
	      }
	    }
	 
	    return result;
	  }
	 
	  /**
	   * 判斷 n 是否能被整除
	   *
	   * @param n   要判斷的數(shù)字
	   * @param primes 包含素?cái)?shù)的列表
	   *
	   * @return 如果 n 能被 primes 中任何一個(gè)整除，則返回 true。
	   */
	  private static boolean divisible(int n, List<Integer> primes) {
	    for (Integer prime : primes) {
	      if (n % prime == 0) {
	        return true;
	      }
	    }
	    return false;
	  }
	}

第一種和第二種都是很簡(jiǎn)單的方法：
第三種方法說(shuō)明了一個(gè)質(zhì)數(shù)的特性：在所有質(zhì)數(shù)中，只有2是偶數(shù)。
如果一個(gè)數(shù)能夠被它之前的質(zhì)數(shù)整除，那么這個(gè)數(shù)不是質(zhì)數(shù)。

您可能感興趣的文章: