⚠️TIPS:所有的代码均为思想，仅供参考使用

最大公约数：

int gcd(int a, int b)
{
  return (a % b == 0) ? b : gcd(b, a % b);
}

极简版：

int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}

最小公倍数：

int lcm(int a, int b)
{
  return a / gcd(b, a % b) * b;
}

朴素写法:

bool isprime(int x)
{
  if(x < 2) return 0;
  for(int i = 2; i <= x / i; i++)
    if(x % i == 0)
      return 0;
  return 1;
}

埃氏筛（memset）

无p数组的版本

int n, cnt = 0;
bool a[100000005];

void sf(int x)
{
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= x; i++)
  {
    if(a[i] == 1)
    {
      cnt++;
      for(int j = i + i; j <= x; j += i)
      {
        a[j] = 0;
      }
    }
  }
}

有p数组的版本

const int N = 10000005;
int n, p[N], cnt = 0;
bool a[N];

void sf(int x)
{
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= n; i++)
  {
    if(a[i])
    {
      p[++cnt] = i;
      for(int j = i + i; j <= n; j += i)
        a[j] = 0;
    }
  }
}

欧拉线性筛

const int N = 10000005;
int n, p[N], cnt = 0;
bool a[N];
void sf(int n){
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= n; i++)  {
    if(a[i]) p[++cnt] = i;
    for(int j = 1; j <= cnt && p[j] * i <= n; j++){
      a[p[j] * i] = 0;
      if(i % p[j] == 0) break;
    }
  }
}

举个例子（思想）： 1-8

0 1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1

0 1 2 3 4 5 6 7 8
0 0 1 1 1 1 1 1 1

    i
0 1 2 3 4 5 6 7 8
0 0 1 1 1 1 1 1 1

p[] ->
2
        2
0 1 2 3 4 5 6 7 8
0 0 1 1 0 1 1 1 1

以此类推

代码对应(核心)

for(int j = 1; j <= cnt && p[j] * i <= n; j++)
{
      a[p[j] * i] = 0;
      if(i % p[j] == 0) break;
}