分解质因数

neuq031220 · 2023-09-10 20:38:03 · 个人记录

• 质数定理：1到n中质数个数约为n/ln(n)
• 分解质因数（朴素） acwing

  #include <bits/stdc++.h>
  using namespace std;
  void solve()
  {
  int x;
  cin >> x;
  for(int i = 2;i <= sqrt(x);i ++)
  {
      if(x%i == 0)
      {
          int cnt = 0;
          while(x % i == 0)
          {
              x /= i;
              cnt ++; 
          }
          cout << i << ' ' << cnt << endl;        
      } 
  }
  if(x > 1)
  cout << x << ' ' << 1 << endl;
  cout << endl;
  }
  int main()
  {
  int n;
  cin >> n;
  while(n --)
  {   
      solve();
  }
  return 0;
  }

• 只需要试除小于根号n的质数
• acwing

  #include <bits/stdc++.h>
  #define int long long
  using namespace std;
  const int N = 1e5 + 10;
  int a0, a1, b0, b1, ans;
  int check(int x)
  {
  int g = __gcd(x, a0);
  if(g != a1) return 0;
  if(x * b0 / __gcd(x, b0) != b1) return 0;
  return 1;
  }
  int st[N], prime[N], cnt;
  void pre(int n)
  {
  for(int i = 2;i <= n;i ++)
  {
      if(!st[i]) prime[cnt ++] = i;
      for(int j = 0;prime[j] * i <= n;j ++)
      {
          st[prime[j] * i] = 1;
          if(i % prime[j] == 0) break;
      }
  }
  }
  vector<pair<int,int> > q;
  vector<int> dv;
  void dfs(int num,int va)
  {
  if(num > q.size() && check(va))
  {
      ans ++;
  }
  if(num > q.size()) return ;
  int p = q[num-1].first, c = q[num-1].second;
  int res = 1;
  for(int i = 0;i <= c;i ++)
  {
      if(i)
      res *= p;
      dfs(num + 1, va * res);
  }
  }
  signed main()
  {
  int n;
  cin >> n;
  pre(1e5);
  while(n --)
  {
      q.clear();
      dv.clear();
      ans = 0;
      cin >> a0 >> a1 >> b0 >> b1;
      int va = b1;
      for(int i = 0;i < cnt;i ++)
      {
          int p = prime[i], c = 0;
          if(va % p == 0)
          {
              while(va % p == 0)
              {
                  va /= p;
                  c ++;
              }
              q.push_back({p, c});
          }
      }
      if(va > 1) q.push_back({va, 1});
      dfs(1, 1);
      cout << ans << endl;
  }
  return 0;
  }