Java实现求小于n的质数的3种方法

网友投稿 215 2023-08-03


Java实现求小于n的质数的3种方法

质数概念

质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。

最小的素数是2,也是素数中唯一的偶数;其他素数都是奇数。质数有无限多个,所以不存在最大的质数。

一:根据定义去求解:

也是最笨的方式,效率比较低:

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){

http://break;

}

}

}

}

}

2:平方根:

package test.ms;

public class Prime {

public static void main(String[] args) {

for(int UcrQIOUNj = 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:找规律(摘自一个论坛讨论)

最小的素数是2,也是素数中唯一的偶数;其他素数都是奇数。质数有无限多个,所以不存在最大的质数。

package test.ms;

import java.util.ArrayList;

import java.util.Listhttp://;

public class Primes {

public static void main(String[] args) {

// 求素数

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 以内的所有素数

*

* @param n 范围

*

* @return n 以内的所有素数

*/

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 要判断的数字

* @param primes 包含素数的列表

*

* @return 如果 n 能被 primes 中任何一个整除,则返回 true。

*/

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

for (Integer prime : primes) {

if (n % prime == 0) {

return true;

}

}

return false;

}

}

第一种和第二种都是很简单的方法:

第三种方法说明了一个质数的特性:在所有质数中,只有2是偶数。

如果一个数能够被它之前的质数整除,那么这个数不是质数。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Java中的递归详解(用递归实现99乘法表来讲解)
下一篇:Windows下java、javaw、javaws以及jvm.dll等进程的区别
相关文章

 发表评论

暂时没有评论,来抢沙发吧~