素数

Prime

• 素数的实现有很多种，性质也很多
• 用于直接判断，查找，构成其他数字等都可能出现，主要在于抽象或联想到素数问题

实现

试除法

• 时间复杂度是 $O(\sqrt{n})$

  bool is_prime(int n)
  {
		if(n < 2)  return false;
		else
	  {
			for(int i = 2; i  <= n / i; i ++) // n / i 是i对应的另一个约数，此为最简最快的判断条件
			if(n / i == 0)  return false;
	  }
	
	return true;
  }

质因数分解

性质

• 任何合数（非质数的数）都可以拆成多个质因数的乘积
• 如 30 = 2 * 3 * 5
• 求解质因数
• 从最小的质因数开始分解，做短除，一直除到没得除了再找更大的质因数

  void devide(int n)
  {
		for(int i = 2; i <= n; i ++)
	  {
			if(n % i == 0)  //找到质数
		  {
				while(n % i == 0) //短除
			  {
					n /= i;
					s ++;  // 记录短除次数，即该因数的指数
			  }
		  }
			cout << i << s << endl; // 打印出质因数与其次数
	}
  }

注意 为什么可以从2开始直接找质因数，不是要找到质因数，才可以进一步做短除吗？（i为什么是质因数）

• 首先 i 从2开始找，第一个i为质数
• 当找过了i个数，即n已经短除了所有2 ~ i - 1的可能质因数 ，此时当 i 的质因数还有 2 — i - 1 中的数的时候，i 不能整除 n
• 因为n已经除去了所有数，比如 2 当 i 还有 2 这个质因数的时候， i = 2 * m1 * m2 … 等，而 n 不再是2的某个倍数，n % i != 0 ，即无法整除
• 而此时 i 中由于没有 2 - i - 1 的所有数，所以 i 不满足 任何合数都可以化成质因数相乘结果 的定理，所以 i 不是一个合数，为质数

那么有性质二

• n当中最多只有一个大于 $\sqrt{n}$ 的质因数
• 如果有两个，两个相乘就大于n
• 所以代码可以做更改

  void devide(int n)
  {
		for(int i = 2; i <= n / i; i ++)  //改为 sqrt(n)
	  {
			if(n % i == 0)  //找到质数
		  {
				while(n % i == 0) //短除
			  {
					n /= i;  // 这步最后一次整除后，n会等于1，所以最后一次特判要大于1
					s ++;  // 记录短除次数，即该因数的指数
			  }
		  }
			cout << i << s << endl; // 打印出质因数与其次数
	}
	
		if(n > 1)  cout << n << '1' << endl;
		// 如果n还没有被除尽，那么此时的n就是他的大于 sqrt(n) 的质因子
  }

• 时间复杂度 最坏 $O(\sqrt{n})$ 最好 $O(logn)$

质数筛法

• 从2开始，将n中2的倍数删掉，依次遍历删除，剩下的数就是质数
• 因为在删除 i - 1 之前的数的倍数后，如果第 i 个数没有被删，证明它不是 2 - i - 1的倍数，即是质数

void get_prime(int n)
{
	for(int i = 2; i <= n; i ++)
  {
		if(!st[i])  // 该数没有被删
			primes[cnt ++] = n;  // 记下个数
		for(int j = i + i; j <= n; j += i)  st[j] = true;  //删掉该数
  }
}

性质 埃氏筛法

• 有 1~n 中有 $n/lnn$ 个质数（质数定理）
• 发现只删去质数的倍数就够了（合数都是质数积）
• 此时时间复杂度变为$O(nloglogn)$

for(int i = 2; i <= n; i ++)
{
	if(!st[i])
	{
		primes[cnt ++] = n;
		for(int j = i + i;  j <= n; j += i)  st[j] = true;
	}
}

性质 线性筛法

void get_prime(int n)
{
   for(int i = 2; i <= n; i ++)
 {
   	if(!st[i])  primes[cnt ++] = i;
   	for(int j = 0; primes[j] <= n / i; j ++)
     {
   		st[primes[j] * i] = true;  // 删到这个遍历到的质数的倍数
   		if(i % primes[j] == 0)  break;  // 如果i可以被这个质数整除，就退出
     }
}
}

• 首先找质数，在目前找到的质数范围内，遍历质数集合，用一个合数的最小质数来删除这个合数（即 用 最先遍历到的 p[j] 来 删除 p[j] * i 这个合数）
• 当 i % p[j] = 0 退出，是因为当 i 是 p[j] 的倍数时，i中就有一个小于后面所有素数的最小质因数，用 i * p[j] 来删除就会导致不是用最小的质数来删除合数，所以到此就退出
• 同时，找最小质因子来删除合数保证了每一个合数都会被删掉（定理），并且每一个数都只被删除一次，因此是线性的