素数判断

Oscar_Wu · 2023-03-07 22:44:03 · 个人记录

嗨嗨害 第一篇题解来啦

- 素数判断

• 例题

  【题目描述】

  给出一个正整数n，输出1-n所有素数，用空格分开。

  【输入样例】

  100

  【输出样例】

  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

  看到素数判断首先想到……

  方法壹 普通（难度：1/10）

  首先想到素数的性质

  根据小学课本：素数（质数）是只有1和它本身两个因数的数叫做素数

  因此 枚举大法就此出现！！！

  我们想到从2枚举到他本身-1，只要出现一个因数，就立刻停止，判定为不是素数，我们定义一个函数，像这样：

  bool/*返回值为布尔变量*/ is_prime(int x){
  if (x <= 1) return false;//特殊判断，1不是素数 
  if (x == 2) return true;//特殊判断，too 
  for (int i = 2; i <= x - 1; ++i){//从2枚举到x-1 
      if (x % i == 0){//如果能除尽（是因数） 
          return false;//就返回FALSE（不是） 
      }
  }
  return true;//三种情况都不是，就是素数 
  }

  但仔细想想就会发现：时间复杂度太高：O（n^2）

  于是我们就都可以想到，因数是成对出现的，可以只枚举到n/2

  改成：

  bool is_prime(int x){
  if (x <= 1) return false;
  if (x == 2) return true;
  for (int i = 2; i <= x / 2 /*优化*/; ++i){
      if (x % i == 0){
          return false; 
      }
  }
  return true; 
  }

  但，时间复杂度还是差不多，所以可以只枚举到√n （至于为什么我不知道）

  bool is_prime(int x){
  if (x <= 1) return false; 
  if (x == 2) return true;
  //for (int i = 2; i <= sqrt(x)/*再优化*/; ++i){
  //但是，众所众知平方根的计算效率是很慢的，不如乘法，SO
  for (int i = 2; i * i <= x; ++i){
      if (x % i == 0){ 
          return false; 
      }
  }
  return true;
  }

  方法贰 埃氏筛（爱氏筛）（难度：5/10）

  第二种方法：我们可以从1开始枚举到n把所有枚举数的倍数（合数）全部标记（删除）

  注：此方法仅适用于一段范围内

  #include<iostream>
  #include<cstdio>
  using namespace std;
  bool hash[1005] = {false};//建立一个标记数组  
  int ans[1005]; //储存结果 
  int main(){
  int n,cnt = 0/*计数*/;
  cin >> n ;
  for (int i = 2; i <= n; ++i){
      if (hash[i]) continue;//如果已被标记为合数，直接下一个  
      for (int j = i; j <= n / i; ++j){//枚举  
          hash[i * j] = true;//标记合数 
      }
      ans[cnt++] = i;//不是合数，加入素数组  
  }
  --cnt;
  cout << 2 << ' ' ;//特殊待遇 
  for (int i = 1; i <= cnt; ++i){
      cout << ans[i] << ' ' ;
  }//输出 
  return 0;
  }

  好！现在已经完成了埃氏筛！时间复杂度：O(NlnlnN) ——管他咋来的

  但，他是完美的吗？

  NO！

  方法 叁 线性筛（O啦筛 欧拉筛）（难度：8/10）

  闪亮登场！

  首先，我们考虑：埃氏筛其实有重复啊！

  SO，怎样去掉重复呢？

  设我们已经找到了素数数组prime，从2枚举到n，只要用每个素数prime[i]都乘上i,就是所得合数，标记，那个可怜的合数也只被他最小的素因数去除了

  但如果发现i可以除尽该素数，那马上停止，因为继续乘的话后面也一定是该素数的倍数，可有效防止重复！

  #include<iostream>
  #include<cstdio>
  using namespace std;
  bool hash[1005];//建立一个标记数组  
  int prime[1005]; //储存结果 
  int main(){
  int n,cnt = 1;
  prime[1] = 2;
  cin >> n ;
  for (int i = 2; i <= n; ++i){
      if (hash[i] == 0) prime[++cnt] = i;//...
      for (int j = 1; j <= cnt && i * prime[j] <= n/*防止超界*/; ++j){//继续枚举 
          hash[prime[j] * i] = true;
          if (i % prime[j] == 0) break;//避免重复 
      }
  }
  for (int i = 1; i <= cnt; ++i){
      cout << prime[i] << ' ' ;
  }
  return 0;
  }

  时间复杂度：O（n）左右