# Prime Algorithm
{%hackmd theme-dark %}
----
## 質數在數論當中為基本單元
## 在程式設計領域當中亦相當重要
---
## 質數的定義
----
### 除了1與自己以外沒有別的因數
### 稱為質數
### 1不是質數也不是合數
---
### 最基本的質數判定法
```cpp=
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
bool is_prime = true;
if (n == 1)
cout << "not a prime" << endl;
else {
for (int i = 2; i < n; i++) {
if (n % i == 0) {
cout << "not a prime" << endl;
is_prime = false;
break;
}
else {
continue;
}
}
if (is_prime) cout << "is a prime" << endl, is_prime = true;
}
}
}
```
---
### 簡單的優化
```cpp=
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
bool is_prime = true;
if (n == 1)
cout << "not a prime" << endl;
else {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
cout << "not a prime" << endl;
is_prime = false;
break;
}
else {
continue;
}
}
if (is_prime) cout << "is a prime" << endl, is_prime = true;
}
}
}
```
{"metaMigratedAt":"2023-06-15T12:44:12.119Z","metaMigratedFrom":"YAML","title":"Prime Algorithm","breaks":true,"slideOptions":"{\"spotlight\":{\"enabled\":false}}","contributors":"[{\"id\":\"5b103006-4946-4e27-87aa-2ce75fd5fc72\",\"add\":1095,\"del\":1}]"}