[Summary][Math Theory]欧拉系列算法(Updating)

最近温习了一些有关于数论的算法,总结一下。

筛法求素数

(1)埃斯托拉尼筛法 时间复杂度 空间较小

就是最朴素的筛法啦。

#include<cstdio>
bool pri[50000001];
int main()
{
    int n , tot = 0;
    scanf("%d" , &n);
    register int i , j;
    for(i = 2 ; i <= n ; ++i)
    {
        if (!pri[i])
        {
            ++tot;
            for(j = i ; j <= n ; j += i)
                pri[j] = 1;
        }
    }
    printf("%d" , tot);
    return 0;
}

(2)欧拉线性时间筛法 时间复杂度 空间耗费较多

#include<cstdio>
#include<cstring>
const int N = 50000001;
bool f[N];
int pri[3002000] , tot;
int main()
{
    int n;
    scanf("%d" , &n);
    register int i , j;
    f[1] = 1;
    for(i = 2 ; i <= n ; ++i)
    {
        if (!f[i])
            pri[tot++] = i;
        for(j = 0 ; j < tot ; ++j)
        {
            if (i * pri[j] > n)
                break;
            f[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
    printf("%d" , tot);
    return 0;
}

欧拉函数

欧拉函数表示不超过n的正整数中与n互质的正整数的个数。

求欧拉函数

int get_eular(int n)
{
  int ans = n;
  int m = int(sqrt(n + 0.5));
  for(int i = 2 ; i <= n ; ++i)
  {
      if (n % i == 0)
      {
          ans = ans / i * (i - 1);
          while(n % i == 0)
            n /= i;
      }
  }
  if (n > 1)
    ans = ans / n * (n - 1);
  return ans;
}

比较垃圾的递推求欧拉函数 时间复杂度同埃斯托拉尼筛法。

const int N = 100001;
int phi[N];
int i , j , n;
for(i = 2 ; i <= n ; ++i)
    phi[i] = 0;
phi[1] = 1;
for(i = 2 ; i <= n ; ++i)
{
    if (!phi[i])
  {
      for(j = i ; j <= n ; j += i)
      {
          if (!phi[j])
            phi[j] = j;
          phi[j] = phi[j] / i * (i - 1);
      }
  }
}
comments powered by Disqus