质数

大于1的自然数,只能被1和它本身整除的数就是质数。
任何一个合数都能表现成多个质数的乘积。

判断质数

很明显判断一个数是不是质数,我们只需要判断它只有1和它本身这两约数。

试除法

  • 朴素做法

    • 判断一个数x是否是质数,就枚举小于x的数去试除法。
    • 
      	for (int i = 2; i < x; ++ i) {
      	    if (x % i == 0) {
      	        cout << "No prime" << endl;
      	        break;
      	    }
      	}
      
    • 这里很明显有个缺点,当x是一个非常大的质数的时候,必须把2~x的所有数枚举一遍,这是非常耗时的。
  • 优化版做法

    • 
      	for (int i = 2; i <= x / i; ++ i) {
      	    if (x % i == 0) {
      	        cout << "No prime" << endl;
      	        break;
      	    }
      	}
      
    • 问:为什么可以将循环优化到 x/i 次。
    • 答:假设 d | x, 那么 必然存在 (x/d) | x, 我们设 d <= (x/d) <=> d <= sqrt(x), 所以,在sqrt(n), 范围内我们就已经能判断出它是否是质数了。

题目链接试除法判定质数

分解质数

分解出组成该合数的质数。通过试除法。

  • 前提
    • n 中最多只包含一个大于 sqrt(n) 的质素。因为,当有两个的时候,相乘就大于n了。所以我们只枚举到 sqrt(n),

    • 任何一个合数都可以表示为 ${p1a *p2b... pk^k}$ 的质数相乘的表示

  • 模板
    • 
      	for (int i = 2; i <= x / i; ++ i) {
      	    if (x % i == 0) {
      	        // 除尽当前质数
      	        while(x % i == 0) {
      	            x /= i;
      	        }
      	        cout << "prime: " + << i << endl;
      	    }
      	}
      	// 如果x大于1说明,此时x是最大的质数
      	if (x > 1) {
      	    cout << "prime: " << x << endl;
      	}
      

题目链接分解质因数

质数的筛选

埃式筛法

每次都将质数的倍数筛去,因为质数的倍数必然能被当前质数整数。

  • 
    
    	bool primes[N];
    
    	for (int i = 2; i <= n; ++ i) {
    	    if (!primes[i]) {
    	        primes[i] = true;
    	        for (int j = i + i; j <= n; ++ j) 
    	            primes[j] = true;
    	    }
    	}
    
  • 埃式筛选的缺点,重复筛选同一个元素。比如说 2 把 6 筛去,3 也会把 6 在筛一遍。解决这个问题通过线性筛选。

线性筛法

线性说明时间复杂度是 O(n) 的。它把每个数只筛选一次。每次通过该数的最小质因素把它筛去。

  • 
      const int N = 1e6 + 5;
    
      bool st[N];
      int primes[N], cnt;
      int n = 0;
    
    
      void ge_primes() {
          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) {
                      st[i] = true;
                      break;
                  }
              }
          }
      }
    
  • 解释一下第二层循环
    • 如果 i 是质数,那么primes[j] * i 的最小质数是primes[j]
    • 如果 i 不是质数,那么 primes[j] * i 的最小质数是primes[j], 当 i % primes[j] == 0 的时候i的最小质数就是此时此刻的primes[j], 这样就保证了每个数只被自己的最小质因数筛一次。

题目链接筛质数