质数

Deuteron @ 2022-02-19 11:29:18

by Rubidium_Chloride @ 2022-02-19 11:30:06

好像有个 \log ^6 还是 \log ^9 的，但是一般 OI 没人用。

by Amore_eterno @ 2022-02-19 11:30:06

@小可爱萌萌哒 判断单个还是一群

by Amore_eterno @ 2022-02-19 11:31:09

@小可爱萌萌哒 一般都是O（n）预处理，O(1)判断

by 正负君 @ 2022-02-19 11:32:18

@小可爱萌萌哒

bool IsPrime(int n)
{
  for(int i=2; i*i<=n; i++)
  {
    if(!n%i)
    {
      return false;
    }
  }
  return true;
}

by Amore_eterno @ 2022-02-19 11:32:27

单个的话用2,3,5,7进行质数测试，一般的范围基本判断不错

by 正负君 @ 2022-02-19 11:32:47

@小可爱萌萌哒 你可以打表

by 正负君 @ 2022-02-19 11:34:25

@小可爱萌萌哒 要说“最低复杂度”，那就是打表 （顺序查找、二分查找都行）

by BlankAo @ 2022-02-19 11:36:54

Miller-Rabin，O(log^2n)，但是有极小错误率

by 正负君 @ 2022-02-19 11:37:48

@正负君 好吧，二分需要一点时间，就用最普通的吧，别找什么 （一群的话，埃氏筛法也不错）

by 正负君 @ 2022-02-19 11:47:33

@小可爱萌萌哒

bool IsPrime(int n)
{
  if(n<2)
  {
    return false;
  }
  if(n==2||n==3)
  {
    return true;
  }
  if(n%6!=1&&n%6!=5)
  {
    return false;
  }
  for(int i=5; i*i<=n; i+=6)
  {
    if(!n%i||!n%(i+2))
    {
      return false;
    }
  }
  return true;
}

这已经是正常算法中最快的了