‘壹’ java语言：请输入一个整数，并判断他是否为素数 急！！ 正在考试
1. 根据概念判断:
如果一个正整数只有两个因子, 1和p，则称p为素数.
public boolean isPrime(int n)
{
if(n < 2) return false;
for(int i = 2; i < n; ++i)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n).
2. 改进, 去掉偶数的判断
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i < n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n/2), 速度提高一倍.
3. 进一步减少判断的范围
定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i*i <= n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(Math.sqrt(n)/2), 速度提高O((n-Math.sqrt(n))/2).
4. 剔除因子中的重复判断.
定理: 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个"素数"因子d.
证明: I1. 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个因子d.
I2. 如果d是素数, 则定理得证, 算法终止.
I3. 令n=d, 并转到步骤I1.
由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
// primes是递增的素数序列: 2, 3, 5, 7, ...
// 更准确地说primes序列包含1->Math.sqrt(n)范围内的所有素数
public boolean isPrime(int primes[], int n)
{
if(n < 2) return false;
for(int i = 0; primes[i]*primes[i] <= n; ++i)
if(n%primes[i] == 0) return false;
return true;
}
5. 构造素数序列primes: 2, 3, 5, 7, ...
由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;
下面程序可以输出素数表.
public class ShowPrimeNumber{
public static int[] getPrimeNums(int maxNum){
int[] primeNums = new int[maxNum/2+1];
int sqrtRoot;
int cursor = 0;
boolean isPrime;
for(int i=2;i<=maxNum;i++){
sqrtRoot = (int)Math.sqrt(i); //取平方根
isPrime = true;
for(int j=0;j< cursor;j++){
if(primeNums[j]>sqrtRoot)
break;
if(i%primeNums[j]==0){
isPrime = false;
break;
}
}
if(isPrime){
primeNums[cursor++] = i;
}
}
int[] result = new int[cursor];
System.array(primeNums,0,result,0,cursor);
return result;
}
public static void main(String[] args) throws Exception{
int maxNum = Integer.parseInt(args[0]);
int[] primeNums = getPrimeNums(maxNum);
System.out.println("共"+primeNums.length+"个素数");
for(int i=0;i< primeNums.length;i++){
System.out.print(primeNums[i]+",\t");
}
}
}
6.(在素数表中)二分查找
Arrays.BinarySearch方法:
该方法用于在指定数组中查找给定的值，采用二分法实现，所以要求传入的数组已经是排序了的。
该方法的基本语法格式为：
Static int binarySearch(byte[] a, byte key)
该方法返回数据中key元素所在的位置，如果没有key元素，则返回key应插入的位置：-（insertion point-1），如数组中的第一个元素就大于key，返回-1。
注：数组的数据类型可以是int[] byte[] short[] float[] long[] double[] char[] Object[]类型。
‘贰’ JAVA求素数：for(j=2;j<=i/2;j++):是什么意思为什么i/2，为什么没有“{”
如上所述，不加{}的for的循环体只有后面紧接的一句，
为什么是i/2，就是i的一半（呵呵貌似白说了哈），当i的一半赋给一个整型的数时，或i/2被当成一个整型的数使用时，它一半就是去掉小数后的数（向下取整，比如5的一半，就当是2）
因此，算法大致的意思是这样，一个3到100的数，如果这个数，都不能被2到这个数的一半的数整除的话，就是素数
------------以下是对补充问题的回答------------------------
第一个if，当i能被j（一个2到i一半的整数）整除的时候，跳出for(j=2;j<=i/2;j++){}循环体，当然for(j=2;j<=i/2;j++){}循环体什么也没做，就一个劲的判断，当判断到有的场合时跳出，没有的话，j递增，然后继续循环
直到循环结束都没出现当i能被j（一个2到i一半的整数）整除的场合时，也跳出循环体，而j的值在结束时加1，刚好大过或等于（i的一半加1）。
而i在以上的两种情况跳出的场合，性质是不一样的，第一种是非素数，第二种是素数，所以进行
第二个if，假如for(j=2;j<=i/2;j++){}循环体是在循环还没结束时跳出的，值必定小于（i的一半加1），就什么也不做，反之，是在循环结束时跳出的，那就是素数，就进行打印，
第三个if，没用{}那么只影响下一句，效果就是每6个素数就分别多用一行空行格开，纯粹格式不用在意
当然，如楼上，所说可以用i的平方根代替，可以减少检验次数
可能没说清楚，可能啰嗦了点，呵呵，希望对你有帮助！
-------------------------------对补充的回答
这两天没上网XD，是的，没有自增
‘叁’ java for循环 求素数
importjava.io.*;
classtest
{
publicstaticvoidmain(String[]args)throwsjava.lang.Exception
{
for(intn=2;n<100;n++){
booleanflag=true;
for(intm=2;m<n;m++){
if(n%m==0){
flag=false;
break;
}
}
if(flag){
System.out.println(n);
}
}
}
}
你自己看下吧，两个for实现。