## 質數 ---- <style> .reveal .slides { text-align: left; } </style> 因數只有 $1$ 和 **自己本身** 的數叫質數。 ---- Example : 輸入一個數，判斷此數是不是質數。 ```cpp= #include<iostream> using namespace std; int main() { int n; bool flag = false; scanf("%d", &n); for(int i=2;i<n;i++) { if(n % i == 0) { flag = true; break; } } if(flag){ printf("NO"); } else{ printf("YES"); } } ``` 最簡單的，我們直接檢查 $2$ ~ $n-1$ 即可。 ---- 跑太多遍?試試這個酷酷的數論。 ---- ```cpp= #include<iostream> #include<math.h> using namespace std; int main() { int n; bool flag = false; scanf("%d", &n); for(int i=2;i<=sqrt(n);i++) { if(n % i == 0) { flag = true; break; } } if(flag){ printf("NO"); } else{ printf("YES"); } } ``` 你會發現，其實只要判斷到 $\sqrt{n}$ 就好了，為何? ---- 當 common sense。