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

質數(shù)概念

質數(shù)，又稱素數(shù)，指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，無法被其他自然數(shù)整除的數(shù)(也可定義為只有1和本身兩個因數(shù)的數(shù))。

最小的素數(shù)是2，也是素數(shù)中唯一的偶數(shù)；其他素數(shù)都是奇數(shù)。質數(shù)有無限多個，所以不存在最大的質數(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ī)律(摘自一個論壇討論)

最小的素數(shù)是2，也是素數(shù)中唯一的偶數(shù)；其他素數(shù)都是奇數(shù)。質數(shù)有無限多個，所以不存在最大的質數(shù)。

package test.ms;

import java.util.ArrayList;

import java.util.List;

public class Primes {

public static void main(String[] args) {

// 求素數(shù)

List primes = getPrimes(1000);

// 輸出結果

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)的所有素數(shù)

*

* @param n 范圍

*

* @return n 以內(nèi)的所有素數(shù)

*/

private static List getPrimes(int n) {

List result = new ArrayList();

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 包含素數(shù)的列表

*

* @return 如果 n 能被 primes 中任何一個整除，則返回 true。

*/

private static boolean divisible(int n, List primes) {

for (Integer prime : primes) {

if (n % prime == 0) {

return true;

}

}

return false;

}

}

第一種和第二種都是很簡單的方法：

第三種方法說明了一個質數(shù)的特性：在所有質數(shù)中，只有2是偶數(shù)。

如果一個數(shù)能夠被它之前的質數(shù)整除，那么這個數(shù)不是質數(shù)。相關閱讀:

Win10預覽版升級為什么總要修復Bug

sqlserver中幾種典型的等待

c#實現(xiàn)md5加密示例

代碼觸發(fā)js事件(click、change)示例應用

CSS3中Animation動畫屬性用法詳解

Windows 10 build 10240再次推送一枚安全更新KB3074683

JavaScript cookie 跨域訪問之廣告推廣

PHP面向對象精要總結

Android Bitmap詳細介紹

在CentOS系統(tǒng)上安裝Eclipse的教程

phplist及phpmailer(組合使用)通過gmail發(fā)送郵件的配置方法

Linux系統(tǒng)命令中exit與exit的區(qū)別

簡單好用的PHP分頁類

Java編寫迷宮小游戲

總結

以上是生活随笔為你收集整理的java求小于n的素数_java_Java实现求小于n的质数的3种方法，质数概念质数，又称素数， - phpStudy...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。