洛谷p1579 +线性筛法（欧拉筛法）的个人理解

先上题目：

一般而言，对于求质数，素数，有三种方法（~~抱歉，是我只知道三种~~）

①首先！最简单的是，对一个数从2到其平方跟，检测是否能够整除，均不能被整除，素数出现！

bool prime(int x)
{
    for (int j=2;j<=sqrt(x);j++)
    if (x%j==0) return false;
    return true;
}

②其次，就是埃氏筛法了，通过将已有的质数进行倍数放大，得到的数必然不是素数，然后逐个质数进行放大，最终取其补集即可！额，对了，0,1除外，这辆不是素数也不是合数。

void Prime()  
{  
    for (int i=0; i<MAXN; i++) prime[i]=1;  //先把每个数都定义为合数
    prime[0]=prime[1]=0;  
    for (int i=2; i<MAXN; i++)  
    {  
        if (!prime[i]) continue;  
        for (int j=i*2; j<MAXN; j+=i) prime[j] = 0;  //将i的倍数标记为合数
    }  
}

③最后，那就本次的重点了！线性筛法，亦称欧拉筛法

void Pn() {//先把质数表做出来
 pn[0] = 2;
 for (int i = 3; i < 20000; i++) {
  bool flag=true;
  for (int j = 0; j < x; j++) {
   if (i % pn[j] == 0) {
    flag = false;
    break;//能被一个最小的素数整除，非素数
   }
   
  }
  if (flag) {
   pn[x++] = i;
  }
 }
}

分析：pn用来存取，所有已经获取的质数，x则为已获取的所有质数的个数，从3开始，遍历质数表，3不能整除任何素数，则3也是一个素数。（此处补充一个数学原理：所有的合数均存在一个最小质数因子，就像6，它的因子有1,6,2,3，而2就是它的最小质数因子）

每次整除一个最小的质数将会跳出循环，所以每个数字，只会被最小的质数筛一次（非常重要！！核心思想！！），所以整个

算法的时间复杂度接近于o(N).

THEN!

回过来，看看题目，我只要加个搜索就好了，找到我就停。

#include <iostream>
#include <cmath>
#include <iomanip>


using namespace std;

//p1579,分析：先做出质数表，然后通过dfs来找出匹配三个质数。

int pn[20000];//用于记录已有的素数
int x=1;//记录素数的个数
int sum;//记录和
int ans[3] = {0};//记录三个加数所属的质数位置
//int used[20000] = { 0 };//记录该质数是否被使用过

void Pn() {//先把质数表做出来
 pn[0] = 2;
 for (int i = 3; i < 20000; i++) {
  bool flag=true;
  for (int j = 0; j < x; j++) {
   if (i % pn[j] == 0) {
    flag = false;
    break;//能被一个最小的素数整除，非素数
   }
   
  }
  if (flag) {
   pn[x++] = i;
  }
 }
}
bool flag = false;
void dfs(int count) {
 if (flag) {//已经找到则无需再找
  return;
 }
 if (count == 3) {//到了个数就判断是否满足
  if (pn[ans[0]]+pn[ans[1]]+pn[ans[2]] == sum) {
   flag = true;
   cout << pn[ans[0]] << " " << pn[ans[1]] << " " << pn[ans[2]];
  }
  return;
 }
 for (int i = 0; i < x; i++) {
  /*if (used[i] == 0) {
   used[i] = 1;
   ans[count] = i;
   dfs(count + 1);
   used[i] = 0;
  }*/
  ans[count] = i;
  dfs(count + 1);
 }
}


int main() {
 Pn();
 /*for (int i = 0; i < x; i++)
 {
  cout << pn[i] << " ";
 }*/
 
 cin >> sum;
 dfs(0);

}

原本以为用dfs，后来发现元素可以重用，简单搜索即可。

补充一种质数判断的方法：

bool isprime(int num) {//原理除了2,3，所有的质数都围绕正在6的左右，但不一定是质数
 if (num <= 1) {//0,1非质数排除掉
  return false;
 }
 if (num==2||num==3) {//2,3为质数
  return true;
 }
 if (num % 6 != 1 && num % 6 != 5) {//不在6左右的必然不是质数
  return false;
 }
 //如果该数能被5,7,11,13。。。（即6的倍数的左右两值）整除，则非质数
 for (int j = 5; j <= sqrt(num); j += 6) {
  if (num % j == 0 || num % (j + 2) == 0) {
   return false;
  }
 }
 //其余皆为质数
 return true;

}