###### tags: `Java`
# Java自學紀錄 - 質數篩法
## 學習重點
* for迴圈
* 陣列
* 質數篩法

### 陣列運用

(資料型別) (陣列名稱)[索引1] = new (資料型別) [陣列大小]
example:
int prime[] = new int[10000000];

# 質數篩法
>一般我們求質數可以用兩個for迴圈,第二個for來判斷有沒有第一個for跑的數字的因數
>**沒有的話就是質數**,但是當詢問數字很大,例如```1e7```:程式就會跑(1e7)^2^次
>複雜度為 n^2^
>所以這時候質數篩法就派上用場了
#### 步驟
1. 先宣告陣列```prime[1000005];```
2. 當``prime[i]``為質數其值為``0``,否則為``1``
3. 輸入一個值,就可直接從``prime[]``中找答案

import java.util.Scanner;

public class Java質數篩法 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int prime[] = new int [10000000];  //宣告陣列
        for(int i=2;i*i<=10000000;i++){
            if(prime[i]==0) {  // ==0代表是質數
                for (int j=i+i;j<10000000;j+=i) {
                    prime[j] = 1;  //將質數的倍數都改成1
                }
            }
        }
        prime[1] = 1;  //1要特別處理
        while(in.hasNext()) {  // 多筆輸入
            int n;
            n = in.nextInt();
            if(n==0) break; //輸入0表程式結束
            if (prime[n] == 0) System.out.println("Prime!");
            else System.out.println("No Prime!");
        }
    }
}

>下圖為執行結果