用java求素数的几种方法与优缺点

Question

求100内的所有素数，这里有三种方法，如下public class Prime {
    public static boolean isPrime(int num){
        for (int i = 2; i < num; i++) {//运行效率不高
            if ((num % i) == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args){
        for(int i = 2; i <= 100; i++) {
            if(isPrime(i)){
                System.out.print(i + " ");
            }
        }
    }
}public class TestPrime {  
public static boolean isPrime(int num) {   
   for(int i = 2; i <= Math.sqrt(num); i++) {//程序默认2是素数，当j=2时，循环不执行
   if(num % i == 0) {
 return false;
   }
   }
   return true;
}
public static void main(String[] args) {
for(int j = 2; j <= 100; j++) {
if(TestPrime.isPrime(j)) {
System.out.println(j + " is a prime");
}
}   
}
}public class PrimeNumber {
//求100内的所有素数（质数）
public static void main(String[] args) {
for(int i = 2;i <= 100;i++) {
for(int j = 2;j <= (int)Math.sqrt(i);j++) {//把Math.sqrt(i)转换为int类形
if(i % j == 0){
break;
}
if(j >= (int)Math.sqrt(i)) {
System.out.println(i + " is a prime");
}
}
}
}
}
第一种和第二种方法都可以输出正确结果，但第三种方法只能输出5以后的数，2和3不能输出来，请各位帮我看下怎么改，
另外，第一种方法看起来简单，但是效率不高，要循环的次数明显多于后面两种，所以第二种方法是最好的方法，也是最容易看懂的方法。

Answer 1

public class address {
//求100内的所有素数（质数）
    public static void main(String[] args)
    {
        for(int i = 2;i <= 100;i++) 
        {
            for(int j = 2;j <= (int)Math.sqrt(i);j++) 
            {//当i=2或者3的时候，此时j=2>sqrt(i),故这个循环不能进去，自然打印不出来2和3了！
                if(i % j == 0)
                {
                    break;
                }
                if(j>= (int)Math.sqrt(i)) 
                {
                     System.out.println(i + " is a prime");
                }
            }  
            
        }
    }
}
知道了问题所在，自己改吧！

Answer 2

归根到底还是算法的问题:
1.小范围内判断一个数是否为质数：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then begin 
prime:=false; exit;
end;
prime:=true;
end; 2.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
procedure getprime;
var 
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i<50000 do begin
if p[i] then begin
j:=i*2;
while j<50000 do begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p[i] then begin
inc(l);pr[l]:=i;
end;
end;{getprime}function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr[i]>=x then break
else if x mod pr[i]=0 then exit;
prime:=true;
end;{prime} 

Answer 3

请问下你这是什么语言写的呢，我不是很懂，刚开始学java,以前就只有点C的知识

Answer 4

改成这样public class PrimeNumber {
//求100内的所有素数（质数）
public static void main(String[] args) {
for(int i = 2;i <= 100;i++) {
for(int j = 2;j <= (int)Math.sqrt(i) + 1;j++) {//把Math.sqrt(i)转换为int类形
if(i % j == 0){
break;
}
if(j >= (int)Math.sqrt(i) + 1) {
System.out.println(i + " is a prime");
}
}
}
}
}
但只能输出3，2还是不能输出，是不是要再写一个if,

Answer 5

public class PrimeNumber {
// 求100内的所有素数（质数）
    public static void main(String[] args) {
        for(int i = 2;i <= 100;i++) {
            for(int j = 2;j <= (int)Math.sqrt(i) + 1;j++) {//把Math.sqrt(i)转换为int类形                 if(i == 2 && j == 2)
                {
                 System.out.println(j + " is a prime");
                 continue;
                }
                
                if(i % j == 0){
                    break;
                }
                
                if(j >= (int)Math.sqrt(i) + 1) 
                {
                 System.out.println(i + " is a prime");
                }
            }    
        }
    }
}

Answer 6

你的项目是用1.6编译的吗，jdk高版本兼容低版本

Answer 7

我觉得效率最高是，把从小到大的计算过的素数保存到linkedlist
这样每次判断素数只需要计算少数几个(平方数不大于当前数字的素数)缺点也很明显，耗费一些空间，而且判断单个素数时也不适用

Answer 8

用Math.sqrt(i)来做第二层循环，效率比较高。
public class Prime {
public static void main(String args[]){
int count = 0;

for (int i=101; i<=200; i+=2){
int k = (int)Math.sqrt(i)+1;

for (int j=2; j<=k; j++){
if (i%j == 0)
break;

if (j >= k){
System.out.print(i +", ");
count ++;
}
}
}

System.out.println("\nTotal: "+ count);
}
}

Answer 9

看来Lz还须要努力,好的算法是在不知道结果的情况下做出来的,而不是加几个if让它显示出来
有点掩耳盗铃的感觉(-_-),你要改进你的算法,而不是一味得出结果就算了！
给你说一个很快的方法吧,就是用已知的素数生成未知的素数.见我在下面发的帖子:
http://topic.csdn.net/u/20090404/16/bbf4d3c3-5030-4e9f-9aa2-807048ea46de.html

Answer 10

我的第二种和第三种方法就是用的Math.sqrt(i)来做第二层循环，
但是用第三种方法时，不再加个if不会输出2，不知道怎么改下才可以

Answer 11

public class PrimeNumber {
//求100内的所有素数（质数）
    public static void main(String[] args)
    {
        for(int i = 2;i <= 100;i++)
        {
         int temp=(int)Math.sqrt(i);
                //我把那个aqrt单独提出来,这样速度稍微快一点,虽然在100内变化不大,但如果是10000000内的素数呢?
         if(i<=3)//上面我说过,是由于<sqrt(i),那么加个if判断一下就OK了，有那么难么?
         {
         System.out.println(i + " is a prime");
         }
         else
         {
                for(int j = 2;j <= temp;j++) 
                {//把Math.sqrt(i)转换为int类形
                   if(i % j == 0)
                   {
                      break;
                   } 
                   if(j >=temp) 
                   {
                     System.out.println(i + " is a prime");
                   }
                }
            
            }
        }
    }
}

Answer 12

我明白你的意思，并且6楼已经做出加入if的方法了，我现在想要的是不再加if，只是改变i和j的值，直接达到正解输出的效果，不知道有没有什么办法。

Answer 13

效率最高的办法还是将之前算出来的素数保存起来，供下一轮检验用。
public class Primes {    public static void main(String[] args) {
        // 求素数
        List<Integer> primes = getPrimes(100000);        // 输出结果
        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<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      要判断的数字
     * @param primes 包含素数的列表
     *
     * @return 如果 n 能被 primes 中任何一个整除，则返回 true。
     */
    private static boolean divisible(int n, List<Integer> primes) {
        for (Integer prime : primes) {
            if (n % prime == 0) {
                return true;
            }
        }
        return false;
    }
}

Answer 14

谢谢，不过，我刚学java，有点不太懂这个程序啊

Answer 15

fortran？！没学过。。不过看着有点像。。

Answer 16

《Core Java》里给出的算法，效率比较高。
统计2000000以内的所有的素数。import java.util.*;/** 
    This program runs the Sieve of Erathostenes bench.
    It computes all primes up to 2,000,000. 
*/public class Sieve
{  
   public static void main(String[] s)
   {  
      int n = 2000000;
      long start = System.currentTimeMillis();
      BitSet b = new BitSet(n + 1);
      int count = 0;
      int i;
      for (i = 2; i <= n; i++)
         b.set(i);
      i = 2;
      while (i * i <= n)
      {  
         if (b.get(i))
         {  
            count++;
            int k = 2 * i;
            while (k <= n)
            {  
               b.clear(k);
               k += i;
            }
         }
         i++;
      }
      while (i <= n)
      {  
         if (b.get(i))
            count++;
         i++;
      }
      long end =  System.currentTimeMillis();
      System.out.println(count + " primes");
      System.out.println((end - start) + " milliseconds");
   }
}

Answer 17

public class PrimeNumber {
//求100内的所有素数（质数）
    public static void main(String[] args) {
        for(int i = 2;i <= 100;i++) {
            for(int j = 1;j <= (int)Math.sqrt(i);j++) {//把Math.sqrt(i)转换为int类形
                if((i % j == 0)&(j>=2)){
                    break;
                }
                if(j >= (int)Math.sqrt(i)) {
                System.out.print(i + " ");
                }
            }    
        }
    }
}
可以输出2和3了，不过我有些不清楚其中的原理。

Answer 18

public static void main(String[] args)
{
for(int i = 2;i < 101;i++)
{int j;
for( j = 2;j <=i/2;j++)
{
if(i%j==0)
break;
}

if(j > i/2)
System.out.println(i+"是素数");


}


}
这种方法可以解决不出现2和3 的问题

Answer 19

 int j;
  for(int i=1; i<=100; i++)
  {
for(j=2; j<=(int)Math.sqrt(i); j++)
{
if(i%j == 0)
break;
}
if(j>=(int)Math.sqrt(i)+1)
{
System.out.print(i+"  ");
}
  }

Answer 20

public class testhello {
public static void main(String args[]){
System.out.println("hello");
enumplus.eplus();
}
}
class enumplus{
public static void eplus(){
for (int i = 2; i <= 100; i++) {
int flag=0;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i%j==0) {
flag=1;
break;
}
}
if (flag==0) {
System.out.println(i);
}
}
}
}

Answer 21

第三种方法是因为2和3根本就无法执行for循环 所以无法输出  我也遇到了同样的问题!

Answer 22

#include <stdio.h>
#include <math.h>
int isPrim(int m);
void printPrim(int m, int n);
int main(void)
{
    printPrim(300, 500);
    return 0;
}int isPrim(int m)
{
    int i;    if (m > 1)
    {
        for (i = 2; i <= sqrt(m); i++)
        {
            if (m % i == 0)
                return 0;
        }
    }
    else if (m == 1 || m == 0)
        return 0;    return 1;
}void printPrim(int m, int n)
{
    int i;
    int cnt = 0;
    for (i = m; i <= n; i++)
    {
        if (isPrim(i))
        {
            printf("%3d ", i);
            cnt++;
            if (cnt % 10 == 0)
                printf("\n");
        }
    }
}

Answer 23

 public class TestClass { 
 //求100内的所有素数（质数） 
  public static void main(String[] args) { 
  for(int i = 2;i  <= 100;i++) { 
  for(int j = 1;j  <= (int)Math.sqrt(i);j++) {//把Math.sqrt(i)转换为int类形 
  if((i % j == 0) && j >= 2){ 
  break; 
  } 
  if(j >= (int)Math.sqrt(i)) { 
  System.out.println(i + " is a prime"); 
  } 
  }  
  } 
  } 
 }
完整代码如上