Bình luận

• 
  

  0

  nguyenquocphonng    6:03 p.m. 29 Tháng 8, 2024

  def prime_factors(n):
  """Trả về một danh sách các thừa số nguyên tố của n và số mũ của chúng"""
  i = 2
  factors = []
  while i * i <= n:
  count = 0
  while (n % i) == 0:
  n //= i
  count += 1
  if count > 0:
  factors.append((i, count))
  i += 1
  if n > 1:
  factors.append((n, 1))
  return factors

  def count_divisors(factors):
  """Tính số lượng ước số dựa trên thừa số nguyên tố"""
  count = 1
  for _, exp in factors:
  count *= (exp + 1)
  return count

  def main():
  import sys
  input = sys.stdin.read
  N = int(input().strip())
  sai rồi bạn ê
  # Phân tích thừa số nguyên tố
  factors = prime_factors(N)

  # Xuất kết quả phân tích thừa số nguyên tố
  factor_strings = []
  for base, exp in factors:
      factor_strings.extend([str(base)] * exp)
  
  print('*'.join(factor_strings))
  
  # Tính số lượng ước số
  divisors_count = count_divisors(factors)
  print(divisors_count)
  

  if name == "main":
  main()

• 
  

  1

  vietnammuonnam_mvn    6:21 p.m. 27 Tháng 8, 2024 ← chỉnh sửa 3 →

  Code cho ai ko bt làm:
  def prime_factorization(n):
  factors = []
  count = 0

  # Phân tích số nguyên tố 2
  while n % 2 == 0:
      factors.append(2)
      n //= 2
      count += 1
  
  # Phân tích các số nguyên tố lẻ
  for i in range(3, int(n**0.5) + 1, 2):
      while n % i == 0:
          factors.append(i)
          n //= i
          count += 1
  
  # Nếu số nguyên tố còn lại là một số nguyên tố lớn hơn 2
  if n > 2:
      factors.append(n)
      count += 1
  
  return factors
  

  def count_divisors(factors):
  from collections import Counter
  factor_count = Counter(factors)
  num_divisors = 1
  for count in factor_count.values():
  num_divisors *= (count + 1)
  return num_divisors

  def main():
  import sys
  input = sys.stdin.read
  n = int(input().strip())

  factors = prime_factorization(n)
  factor_string = '*'.join(map(str, factors))
  num_divisors = count_divisors(factors)
  
  print(factor_string)
  print(num_divisors)
  

  if name == "main":
  main()

• 
  

  -9

  tk22dangminhduc    9:43 p.m. 11 Tháng 7, 2023

  một phiên bản dễ hơn của "FACTOR"...mãi vẫn chưa AC được bài đấy:")

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  2

  hieuhfgr    10:41 a.m. 3 Tháng 5, 2023

  mình nghĩ bài này testcases đang yếu '-'

• 
  

  -3

  tienduyyl    5:14 p.m. 15 Tháng 10, 2021 ← đã chỉnh sửa →

  i

• 
  

  -7

  phambinminh12345    5:44 p.m. 12 Tháng 10, 2021

  Hint 1
  Chia dần các ước nguyên tố của n đồng thời tăng biến đếm
  Đưa các ước nguyên tố p và số lần bị chia vào một mảng Xuất các số nguyên tố theo tần số

  Hint 2
  Khi (p | n) thì p∗np=n
  ⇔p là ước của n thì np cũng là ước của n
  Ta có thể chạy tới n−−√ để đếm số ước

  Thay vì thử từng số nguyên tố, ta có thể từng số i tăng dần từ 2 và kiểm tra tính chia hết
  Nếu n không chia hết i thì bỏ qua (vì nó không phải ước nguyên tố)

  Ngược lại ta sẽ thêm số nguyên tố i vào mảng và chia n dần đồng thời tăng số lần chia

  Hint 3
  Có n=pf11×pf22×...×pfkk với fi∈N
  Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈N
  Mỗi ước nguyên tố pi có f′′i cách chọn

  Nên số cách chọn phần tử d là (f′′1+1)×(f′′2+1)×...×(f′′k+1)
  Vậy khi phân tích số nguyên tố từ n ta dễ dàng tìm số ước trong O(log(logn))
  Nhận xét rằng nếu với mọi số nguyên 2≤x≤√n không phải là ước của n thì n là số nguyên tố
  Chạy tới √n hoặc tới khi n=1 để phân tích thừa số nguyên tố

  Nếu sau đó n>1 thì n là số nguyên tố

  Reference AC code | O(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
  Copy
  int main()
  {
  //// Input
  int n = readInt();
  int sqrtn = sqrt(n);

  pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency>
  
  /// p = 2 case
  if (n % 2 == 0)
  {
      divs.push_back(make_pair(2, 0)); /// Add new prime p = (2)
      do divs.back().se++, n /= 2; while (n % 2 == 0);
  }
  
  /// prime > 2 is odd, we dont have to care about even numbers
  for (int i = 3; i <= sqrtn; i += 2)
  {
      if (n % i != 0) continue;
      divs.push_back(make_pair(i, 0)); /// Add new prime p = (i)
      do divs.back().se++, n /= i; while (n % i == 0);
      if (n == 1) break; /// we can divide more
  }
  
  /// n is prime
  if (n > 1) divs.push_back(make_pair(n, 1));
  
  /// Output
  int p = divs.size();
  int count = 1;
  for (int i = 0; i + 1 < p; ++i)
  {
      count *= (divs[i].second + 1);
      while (divs[i].second-->0) cout << divs[i].first << '*';
  }
  count *= (divs.back().second + 1);
  while (divs.back().second-->1) cout << divs.back().first << '*';
  cout << divs.back().first << endl;
  
  cout << count; /// Number of divisors
  return 0;
  

  }

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  -6

  phambinminh12345    5:44 p.m. 12 Tháng 10, 2021

  Hint 1
  Chia dần các ước nguyên tố của n đồng thời tăng biến đếm
  Đưa các ước nguyên tố p và số lần bị chia vào một mảng Xuất các số nguyên tố theo tần số

  Hint 2
  Khi (p | n) thì p∗np=n
  ⇔p là ước của n thì np cũng là ước của n
  Ta có thể chạy tới n−−√ để đếm số ước

  Thay vì thử từng số nguyên tố, ta có thể từng số i tăng dần từ 2 và kiểm tra tính chia hết
  Nếu n không chia hết i thì bỏ qua (vì nó không phải ước nguyên tố)

  Ngược lại ta sẽ thêm số nguyên tố i vào mảng và chia n dần đồng thời tăng số lần chia

  Hint 3
  Có n=pf11×pf22×...×pfkk với fi∈N
  Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈N
  Mỗi ước nguyên tố pi có f′′i cách chọn

  Nên số cách chọn phần tử d là (f′′1+1)×(f′′2+1)×...×(f′′k+1)
  Vậy khi phân tích số nguyên tố từ n ta dễ dàng tìm số ước trong O(log(logn))
  Nhận xét rằng nếu với mọi số nguyên 2≤x≤√n không phải là ước của n thì n là số nguyên tố
  Chạy tới √n hoặc tới khi n=1 để phân tích thừa số nguyên tố

  Nếu sau đó n>1 thì n là số nguyên tố

  Reference AC code | O(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
  Copy
  int main()
  {
  //// Input
  int n = readInt();
  int sqrtn = sqrt(n);

  pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency>
  
  /// p = 2 case
  if (n % 2 == 0)
  {
      divs.push_back(make_pair(2, 0)); /// Add new prime p = (2)
      do divs.back().se++, n /= 2; while (n % 2 == 0);
  }
  
  /// prime > 2 is odd, we dont have to care about even numbers
  for (int i = 3; i <= sqrtn; i += 2)
  {
      if (n % i != 0) continue;
      divs.push_back(make_pair(i, 0)); /// Add new prime p = (i)
      do divs.back().se++, n /= i; while (n % i == 0);
      if (n == 1) break; /// we can divide more
  }
  
  /// n is prime
  if (n > 1) divs.push_back(make_pair(n, 1));
  
  /// Output
  int p = divs.size();
  int count = 1;
  for (int i = 0; i + 1 < p; ++i)
  {
      count *= (divs[i].second + 1);
      while (divs[i].second-->0) cout << divs[i].first << '*';
  }
  count *= (divs.back().second + 1);
  while (divs.back().second-->1) cout << divs.back().first << '*';
  cout << divs.back().first << endl;
  
  cout << count; /// Number of divisors
  return 0;
  

  }

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  -22

  minhtuanitk20    3:53 p.m. 1 Tháng 10, 2021

  bài dễ nhất thế giới

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

  1 phản hồi
• 
  

  30

  SPyofgame    11:02 p.m. 10 Tháng 6, 2020 ← chỉnh sửa 3 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Chia dần các ước nguyên tố của \(n\) đồng thời tăng biến đếm

  Đưa các ước nguyên tố \(p\) và số lần bị chia vào một mảng
  Xuất các số nguyên tố theo tần số

  ---

  Hint 2

  • Khi \((p\ |\ n)\) thì \(p * \frac{n}{p} = n\)

  \(\Leftrightarrow p\) là ước của \(n\) thì \(\frac{n}{p}\) cũng là ước của \(n\)

  Ta có thể chạy tới \(\sqrt{n}\) để đếm số ước

  • Thay vì thử từng số nguyên tố, ta có thể từng số \(i\) tăng dần từ 2 và kiểm tra tính chia hết

  Nếu \(n\) không chia hết \(i\) thì bỏ qua (vì nó không phải ước nguyên tố)

  Ngược lại ta sẽ thêm số nguyên tố \(i\) vào mảng và chia \(n\) dần đồng thời tăng số lần chia

  ---

  Hint 3

  • Có \(n = p_1 ^ {f_1} \times p_2 ^ {f_2} \times ... \times p_k ^ {f_k}\) với \(f_i \in N\)

  Thì \(d = p_1 ^ {f''_1} \times p_2 ^ {f''_2} \times ... \times p_k ^ {f''_k}\) là ước của \(n\) \(\forall f''_i ≤ f_i\) và \(f''_i \in N\)

  Mỗi ước nguyên tố \(pi\) có \(f''_i\) cách chọn

  Nên số cách chọn phần tử \(d\) là \((f''_1 + 1) \times (f''_2 + 1) \times ... \times (f''k + 1)\)

  Vậy khi phân tích số nguyên tố từ \(n\) ta dễ dàng tìm số ước trong \(O(log (log n))\)

  • Nhận xét rằng nếu với mọi số nguyên \(2 ≤ x ≤ √n\) không phải là ước của \(n\) thì \(n\) là số nguyên tố

  Chạy tới √n hoặc tới khi \(n = 1\) để phân tích thừa số nguyên tố

  Nếu sau đó \(n > 1\) thì \(n\) là số nguyên tố

  Reference AC code | \(O(\sqrt n)\) time | \(O(\frac{\log n}{\log(\log n)})\) auxiliary space | Factorization

  C++

  int main()
  {
      //// Input
      int n = readInt();
      int sqrtn = sqrt(n);
  
      pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency>
  
      /// p = 2 case
      if (n % 2 == 0)
      {
          divs.push_back(make_pair(2, 0)); /// Add new prime p = (2)
          do divs.back().se++, n /= 2; while (n % 2 == 0);
      }
  
      /// prime > 2 is odd, we dont have to care about even numbers
      for (int i = 3; i <= sqrtn; i += 2)
      {
          if (n % i != 0) continue;
          divs.push_back(make_pair(i, 0)); /// Add new prime p = (i)
          do divs.back().se++, n /= i; while (n % i == 0);
          if (n == 1) break; /// we can divide more
      }
  
      /// n is prime
      if (n > 1) divs.push_back(make_pair(n, 1));
  
      /// Output
      int p = divs.size();
      int count = 1;
      for (int i = 0; i + 1 < p; ++i)
      {
          count *= (divs[i].second + 1);
          while (divs[i].second-->0) cout << divs[i].first << '*';
      }
      count *= (divs.back().second + 1);
      while (divs.back().second-->1) cout << divs.back().first << '*';
      cout << divs.back().first << endl;
  
      cout << count; /// Number of divisors
      return 0;
  }
  

  1 phản hồi