算法-求质数问题

算法-求质数问题

清晨说ぺ晚安 发布于 2017-04-08 字数 53 浏览 1137 回复 5

使用算法找出前N(例如前200)个质数,要求高效率

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

灵芸 2017-09-08 5 楼

埃拉托斯特尼筛法可以高效的找出任意整数m以内的所有质数,关键在于对于给定的N,如何限定m。
素数定理给出第n个素数的渐进估计为nln(n),所以可以将m先定为nln(n),通过埃拉托斯特尼筛法筛选,即先去掉所有2的倍数,再去掉所有3的倍数、5的倍数……,直到sqrt(m)的倍数,剩余的数均为素数。

如果剩余的素数没有达到m个,适当扩大m的范围至k,对m和k之间的数再用之前的素数筛选一次

浮生未歇 2017-08-15 4 楼

关键点就在于求一个数是否是质数,就先求出它的平方根,之后判断是否能被平方根以内的除1以外的某个自然数整除,如果有能整除的,那么这个数即为合数,没有即为质数。

引用:java 求质数

甜柠檬 2017-07-30 3 楼

现在好像还没有那个叫兽发现关于质数完全正确规律公式!
现在的方法都很大众化,高效的可能是细化判断细节!

public static void main( String [] args ) {
System.out.print( 2 + "," + 3 + "," );
for ( int i = 4 ; i <= 200 ; i++ ) {
if ( existsPrime( i ) ) {
System.out.print(i+",");
i++;
}
}
}
/**
* @Description: TODO( 判断是否为素数 )
* @author leo(Li lele)
* @return boolean
* @throws
*/
public static boolean existsPrime( int num ) {
if ( num <= 1 ) { return false; }
for ( int i = 2 ; i <= Math.sqrt( num ) ; i++ ) {
if ( num % i == 0 ) { return false; }
}
return true;
}

虐人心 2017-07-04 2 楼

PHP版:

 function isPrime($test)
{
$prime = 1;

if ($test % 2 == 0 && $test != 2){
return 0;
}
if ($test == 2 || $test == 3) {
return 1;
}
for ($try = 3; $try < $test; $try++){
if (($test % $try) == 0) {
$prime = 0;
break;
}
}
return $prime;
}

for ($i=1; $i <= 200; $i++) {
if (isPrime($i))
echo $i.PHP_EOL;
}

归属感 2017-05-18 1 楼

import java.util.*;
/**
* @author Administrator
* 所谓合数就是由质数演变而来,那么只需要判断是否能被前面的质数整除就行了
* 当N为1000000时,查找质数,耗时:820毫秒
*/
public class Test2
{
public static void main(String args[])
{
List<Integer> list=new ArrayList<Integer>();
list.add(2);//初始化,设置第一个质数为2
int N=200;//N
for(int i=3;i<=N;i++)
{
boolean IsZhishu=true;
for(Integer j:list)
{
if(j>Math.sqrt(i))//算到i的平方根就够了
break;
if(i%j==0)
{
IsZhishu=false;
break;
}
}
if(IsZhishu)list.add(i);
}
for(Integer k:list)
System.out.println("质数:"+k);
}
}