今天花了一整天的时间在研究java中素数计算的方法，终于给彻底弄懂了！首先，先看看我上午写的错误代码

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

当时真是糊涂了，脑子里的思路就是，素数，就是看这个数除以2一直到这个数的一半（开方更准确，我习惯直接除2了），如果都不能整除，则这个数就是素数，抱着这个思路，就写出了if。。。else。。。其实，错也就错在这了。

if语句判定不是素数，跳出循环，可以！但如果一个数刚开始不能被2 整除，就直接执行else语句判定它是素数，太武断了！（101到200这几个数很巧，我这个程序凑巧判断出来了）而且，我的结果输出一个数好几次，因为else在内层循环里，一直执行。

研究这个错误研究半天，知道错那了，可也不会写这个题了，参考网上的代码 ，结果发现，好多作者犯了和我一样的错误，挑一个典型说一下：

import java.io.*;
class sa {
    public static void main(String []args) throws  IOException {
      int i,j;
      String a;
     BufferedReader str=new BufferedReader(new InputStreamReader(System.in));
     System.out.println("请输入一个数");
     a=str.readLine();
     int b=Integer.parseInt(a);
     if (b==2) { 
    	 System.out.println("是质数"); 
    	 return; 
    	 }
        double  sqr=Math.sqrt(b);
        long tt=Math.round(sqr);
        for(i=2;i<=tt;i++) {
            if (b%i==0){
            System.out.println("不是质数");
           break;
              }else {
             System.out.println("是质数");
          break; 
    } 
      }
 }

先不说代码很复杂了，输入105，显示105是质数！犯了和我一样的错误！具体就不说了。看到一位作者的正确的代码，思路很奇妙：    

public class qisi {
	public static void main(String[] args) {
	int sum = 0;
	for (int i = 101; i <= 200; i++){
	for (int j = 2; j <= i; j++) {
	if (i % j == 0 && i == j) {
	sum++;
	System.out.println(i);
	} else if (i % j == 0 && i != j)
	break;
	}
	}
	System.out.println("101-200 之间有："+sum+"个素数");
}
}

理解了作者的结题思路。感觉自己应该想不到，就又研究了一种思路

public class sushu {
	public static void main(String[] args){
		for(int i = 101;i<200;i++){
			int n=0;
			for(int j=2;j<=i/2;j++){
				if(i%j==0)
				n=n+1;
				}
			if(n==0)
				System.out.println(i);
		}
		}
	}

就是内层for循环与外层for循环之间定义一个变量n，在内层for循环中，如果i%j等于0.n自增，最后判断n的值，如果n等于0，就说明i是素数，相比之下，感觉自己的算法，更简单点。

判断素数的方法还有很多，今天我算是学到了，也知道for循环魅力无穷，但稍不留神，就一错千里了！

素数的定义

素数也叫质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是质数也不是合数）。

一、试除法（判断素数）

试除法顾名思义就是用 2 到 n - 1 的数一个一个试除，如果 n 不能整除这之间所有的数，那么说明它就是素数。这样从 2 试到 n - 1，显然时间复杂度是的，那么有没有方法可以降低时间复杂度呢？答案是肯定有的，可以证明这个循环范围可以缩小到从 2 到 ，那么时间复杂度就缩短到了。

再对循环式子进行稍微的变形，C++代码如下：

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++)   // 这里用 i <= n / i 或 i * i <= n 比 i <= sqrt(n)要好
        if(n % i == 0)
            return false;
    return true;
}

二、埃氏筛法（求一个范围中的所有素数）

试除法的弊端非常明显，如果要求一个范围中的所有素数，用试除法一个一个判断效率就太低了。

埃氏筛法是用于解决这类问题的古老而简单高效的方法，可以快速找到[2, n]中的所有素数。

具体操作是这样的：从2开始寻找素数，每次找到一个素数后就将它的倍数全部筛掉，并将该素数存储到另一个队列（数组）中，不断循环，直至原队列（数组）为空。

时间复杂度为。

C++代码如下：

int primes[N], cnt;   // primes[]存储所有素数
bool st[N];   // st[x]存储x是否被筛掉

void E_sieve(int n){
    for(int i = 2; i <= n / i; i++){
        if(!st[i]){
            primes[cnt++] = i;
            for(int j = 2 * i; j <= n; j += i)   // 这里可以优化成 int j = i * i
                st[j] = true;
        }
    }
}

三、欧拉筛法（埃氏筛法的优化版）

埃氏筛法中，由于一个数可以既是一个素数的倍数，又是另一个素数的倍数，可以发现这会出现重复标记的情况，即同一个数被筛掉了不止一次，浪费操作了。

欧拉筛法就是在埃氏算法的基础上多了判断的步骤，从而消去了这种重复标记的情况，核心思路是用合数中的一个因数筛掉这个合数。

具体操作为：利用已经求得的素数，第一重循环将区间内的数从小到大遍历，第二重循环将已求得的素数从小到大遍历，将这个数和素数的乘积标记为合数。如果一个数能被素数整除，跳出循环。

时间复杂度为。

C++代码如下：

int primes[N], cnt;   // primes[]存储所有素数
bool st[N];   // st[x]存储x是否被筛掉

void Euler_seive(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;   // 如果这个数能被素数整除，跳出循环
        }
    }
}

素数

质数又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。假设一个数字n，现判断其是否为素数。
1.根据定义当 n 只能被 1 和 n 整除的时候他就是素数，换句话说就是 n 不能被 2~n-1 之间的数字整除。

import java.util.Scanner;
public class Test{
    public static boolean isPrime1(int n) {
        for (int i = 2; i < n ; i++) {//计算从2~n-1中是否存在数字可以被n整除 
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args){
    	Scanner sc = new Scannr(System.in);
    	System.out.println("请输入一个数字 ：");
    	int n = sc.next.Int();
    	System.out.println(isPrime1(n));//打印函数的返回值
    }
}    

2.为了简化计算过程我们想到了另外一个办法:
任意一个数字n都可以写成： n = ab—>例如说：8
8 = 18， 8 = 2*4 其中 1，2，4，8 都为 8 的因数 ，在他的除 1 与 8 的因数中必定存在一个数字小于 8/2，所以当 2 ~ n/2 中出现了可以被 n 整除的数字则 n 就不是素数。

import java.util.Scanner;
public class Test{
    public static boolean isPrime2(int n) {
        for (int i = 2; i <= n/2 ; i++) {//计算从2~n/2是否存在数字可以被n整除
            if(n % i == 0) {
                return false;
            }
 ==       }
        return true;
    }
    public static void main(String[] args){
     Scanner sc = new Scannr(System.in);
     System.out.println("请输入一个数字 ：");
     int n = sc.next.Int();
     System.out.println(isPrime1(n));//打印函数的返回值
    }
}   

3.在2的基础之上我们有延伸出了一种办法：
任意一个数字n都可以写成：n = ab—>例如说：8
8 = 18， 8 = 2*4 其中 1，2，4，8 都为 8 的因数 ，在他的除 1 与 8 的因数中必定存在一个数字小于根号8，所以当 2 ~ 根号8 中出现了可以被 n 整除的数字则 n 就不是素数.

import java.util.Scanner;
public class Test{
    public static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n) ; i++) {//在Java中 Math.sqrt(n)求开根号，计算从2~根号8间
            if(n % i == 0) {                      //是否存在数字可以被n整除
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args){
     Scanner sc = new Scannr(System.in);
     System.out.println("请输入一个数字 ：");
     int n = sc.next.Int();
     System.out.println(isPrime1(n));//打印函数的返回值
    }
}  

===================
以上为简单算素数的办法