好得很程序员自学网

<tfoot draggable='sEl'></tfoot>

Java求质数的几种常用算法分析

本文实例讲述了java求质数的几种常用算法。分享给大家供大家参考,具体如下:

1、根据质数的定义求

质数定义:只能被1或者自身整除的自然数(不包括1),称为质数。

利用它的定义可以循环判断该数除以比它小的每个自然数(大于1),如果有能被它整除的,则它就不是质数。

对应代码是:

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

void printprime( int n){ //判断n是否是质数

   boolean isprime= true ; //是否是质数的标志

   for ( int i=n- 1 ;i> 1 ;i—){ //n除以每个比n小比1大的自然数

    if (n%i== 0 ){ //如果有能被整除的,则不是质数

     isprime= false ;

    }

   }

   if (isprime){ //如果是质数,则打印出来

    system.out.print(n+ " " );

    primenumber++; //记录质数的个数

    if (primenumber% 10 == 0 ) //输出10个质数后换行

     system.out.println();

   }

}

2、利用一个定理 ——如果一个数是合数,那么它的最小质因数肯定小于等于他的平方根。例如:50,最小质因数是2,2<50的开根号

再比如:15,最小质因数是3,3<15的开根号

合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数,则它是质数。
上面的定理是说,如果一个数能被它的最小质因数整除的话,那它肯定是合数,即不是质数。所以判断一个数是否是质数,只需判断它是否能被小于它开跟后后的所有数整除,这样做的运算就会少了很多,因此效率也高了很多。

对应代码是:

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

void printprime( int n){ //判断n是否是质数

   boolean isprime= true ; //是否是质数的标志

   int s=( int )math.sqrt(n); //对n开根号

   for ( int i=s;i> 1 ;i—){ //n除以每个比n开根号小比1大的自然数

    if (n%i== 0 ){ //如果有能被整除的,则不是质数

     isprime= false ;

    }

   }

   if (isprime){ //如果是质数,则打印出来

    system.out.print(n+ " " );

    primenumber++; //记录质数的个数

    if (primenumber% 10 == 0 ) //输出10个质数后换行

     system.out.println();

   }

}

3、筛法求质数 ,效率最高,但会比较浪费内存

首先建立一个boolean类型的数组,用来存储你要判断某个范围内自然数中的质数,例如,你要输出小于200的质数,你需要建立一个大小为201(建立201个存储位置是为了让数组位置与其大小相同)的boolean数组,初始化为true。

其次用第二种方法求的第一个质数(在此是2),然后将是2的倍数的数全置为false(2除外),即2、4、6、8……位置上置为false。然后是3的倍数的全置为false(3除外),一直到14(14是200的开平方),这样的话把不是质数的位置上置为false了,剩下的全是质数了,挑着是true的打印出来就行了。

对应代码是:

?

1

2

3

4

5

6

7

8

9

10

11

boolean [] printprime( int range){

   boolean [] isprime= new boolean [range+ 1 ];

   isprime[ 1 ]= false ; //1不是质数

   arrays.fill(isprime, 2 ,range+ 1 , true ); //全置为true(大于等于2的位置上)

   int n=( int )math.sqrt(range); //对range开根号

   for ( int i= 2 ;i<=n;i++) //注意需要小于等于n

    if (isprime[i]) //查看是不是已经置false过了

     for ( int j=i;j*i<range;j++) //将是i倍数的位置置为false

      isprime[j*i]= false ;

   return isprime; //返回一个boolean数组

}

希望本文所述对大家java程序设计有所帮助。

原文链接:http://blog.sina测试数据.cn/s/blog_622e77cc0100n5lm.html

查看更多关于Java求质数的几种常用算法分析的详细内容...

  阅读:14次