质数(素数)

---

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

---

素数的判定

---

判定给定的正整数n,是否是素数

bool isPrime(int n) {
  for (int i = 2; i <= sqrt(n); i++) {
    if (n%i == 0) {
      return false;
    }
  }
  return true;
}

---

素数因子(质数因子)

---

输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）

vector<vector<int>> FindPrimeFactor(int n) {
  vector<vector<int>> res;
  vector<bool> p(n + 1, true);
  for (int i = 2; i <= n; i++) {
    if (p[i] == true) {
      if (n%i == 0) {
        int num = 0;
        int temp = n;
        while (temp%i == 0) {
          temp /= i;
          num++;
        }
        res.push_back({i,num});
      }
      for (int j = i + i; j <= n; j += i) {
        p[j] = false;
      }
    }
  }
  return res;
}

---

n以内的所有素数

---

求1-n之间所有的素数

---

筛法求素数

---

厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的各数写在纸上：
在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。
这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的，所以，后人就把这种方法称作厄拉多塞筛法。
在计算机中，筛法可以用给数组单元置零的方法来实现。具体来说就是：首先开一个数组：a[i]，i=1，2，3，…，同时，令所有的数组元素都等于下标 值，即a[i]=i，当i不是素数时，令a[i]=0 。当输出结果时，只要判断a[i]是否等于零即可，如果a[i]=0，则令i=i+1，检查下一个a[i]。
筛法是计算机程序设计中常用的算法之一。

vector<int> FindPrime(int n) {
  vector<int> res;
  vector<bool> p(n + 1,true);
  for (int i = 2; i <= n; i++) {
    if (p[i] == true) {
      res.push_back(i);
      for (int j = i + i; j <= n; j += i) {
        p[j] = false;
      }
    }
  }
  return res;
}

---

6N±1法求素数

---

任何一个自然数，总可以表示成为如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。
在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为0－1的循环，则2(i+j)-1恰好就是形如6N±1的自然数。

---