面试题 求N以内的质数

Question

如题。小弟面试的时候出的。不会。还请个人帮忙给解决一下。

Answer 1

public static void main(String[] args){ 
int total=0;
int max=2000;
for (int i = 1; i <= max; i += 2) { 
int temp = (int) Math.sqrt(i); 
boolean isPrime = true; 
for (int j = 3; j <= temp; j += 2) { 
if (i % j == 0) { 
isPrime = false; 
break; 
} 
} 
if (isPrime) { 
total++; 
System.out.println(i + " "); 
} 
} 
}

Answer 2

解释一下含义吧，max是到这个数之前的素数。
素数都是单数，所以每次循环只看单数。
计算从3开始到根号i为止，是否有能整除i的。存在则不是素数，跳出循环，继续算下一个。如果不存在，那就是素数，打印出来。这个是最普通的算法，代码简单明了。肯定存在效率更高的算法，就是没那么简单了。

Answer 3

程序中，初值是有问题的，1和2两个有特别的数学定义，不是算法的问题。3开始的都是对的。改成下面那样：
public static void main(String[] args) { int max = 2;
suShu(max);
} private static void suShu(int max) {
if (max < 2) {
System.out.println("不存在小于等于" + max + "的素数");
} else {
System.out.println("小于等于" + max + "的素数有：");
System.out.println("2");
for (int i = 3; i <= max; i += 2) {
int temp = (int) Math.sqrt(i);
boolean isPrime = true;
for (int j = 3; j <= temp; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) { System.out.println(i + " ");
}
}
}
}

Answer 4

原理：
一个数字n，如果不能被2~sqrt(n)中的任何一个数整除，那么n就是一个素数。
代码楼主应该不难实现吧。

Answer 5

我也凑个热闹，基本思想楼上的都说过了，我给个算法
 for(int i=0;i<=N;i++)    //N以内的素数
            for(int j=2;j<=i-1;j++){
                if(i%j==0)
                    break;
                if(j==i-1)
                    System.out.println(i);
          }

Answer 6

质数就是素数，是指只能被本身和1整除的数4楼的这位哥们写的这个代码很全面   它首先判断1是不是质数，然后在用循环判断public static void main(String[] args) {        int max = 2;
        suShu(max);
    }    private static void suShu(int max) {
        if (max < 2) {
            System.out.println("不存在小于等于" + max + "的素数");
        } else {
            System.out.println("小于等于" + max + "的素数有：");
            System.out.println("2");
            for (int i = 3; i <= max; i += 2) {
                int temp = (int) Math.sqrt(i);
                boolean isPrime = true;
                for (int j = 3; j <= temp; j += 2) {
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {                    System.out.println(i + " ");
                }
            }
        }
    }

Answer 7

http://blog.csdn.net/yidinghe/archive/2009/04/08/4053585.aspx

Answer 8

程序是可以优化的。离散数学或是组合数学中有个定理，大概的意思就是，任何正整数都可以分解为质数的乘积,比如20=2*2*5所以在计算N是否为质数的时候，只要判断能否被N-1之前且小于sqrt(N)的质数整除就可以了, 不必从2到sqrt(N)都判断一遍。

Answer 9

public static boolean isPrimes(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

Answer 10

public class PrimeTest {
public static void main(String[] args) {
int n=100;  /*表示n内的素数*/
Boolean[] prime=new Boolean[n+1];
long count=0; /* 计数器*/
/*prime数组初始化，偶数标志为true,奇数标志为false*/
for(int i=0;i<=n;i++)
if((i&1)!=0) prime[i]=true;
else prime[i]=false;
/*开始筛选*/
for(int i=3; i<=(int)Math.sqrt(n); i+=2 )
      {   if(prime[i]) 
          for(int j=i+i;j<=n;j+=i ) prime[j]=false;
      }

/*输出结果*/
for(int i=0;i<=n;i++){
if(prime[i]){
System.out.print(i+" ");
count++;
}
}
System.out.println();
System.out.println("totally:"+count);
}
}