Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Prime Factorization

Break a number into its prime factors, listed from smallest to largest with repetition.

Bạn sẽ học được gì

  • Divide out each factor as many times as it occurs
  • Stop trial division once d × d exceeds what is left
  • Recognise that a leftover above 1 is a prime factor

Đề bài

Xem bản dịch

Every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors (the fundamental theorem of arithmetic). For example, 360 = 2 × 2 × 2 × 3 × 3 × 5. Finding that list is called prime factorization.

Implement prime_factorization(n).

n can be as large as 10^12, so the classic approach is trial division: divide out 2 as long as you can, then 3, and so on. You only need to try divisors d while d × d ≤ the part of n that is still left; whatever remains above 1 at the end is itself prime. That keeps the work to about √n ≈ 10^6 steps even when n is a large prime or the product of two large primes.

Input

n: The number to factor.

Output

Return the prime factors of n in ascending order, repeating each prime as many times as it divides n, so that the product of the list is n. For n = 1 return an empty list. If n is prime, the list has the single element n.

Ràng buộc

1 ≤ n ≤ 10^12

Ví dụ

Ví dụ 1
Đầu vào:
n = 360

Kết quả mong đợi:
expected = [2, 2, 2, 3, 3, 5]
Đầu vào:
long long n = 360;

Kết quả mong đợi:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Đầu vào:
long n = 360;

Kết quả mong đợi:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

Giải thích

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, so the answer is [2, 2, 2, 3, 3, 5].

Ví dụ 2
Đầu vào:
n = 97

Kết quả mong đợi:
expected = [97]
Đầu vào:
long long n = 97;

Kết quả mong đợi:
std::vector<long long> expected = {97};
Đầu vào:
long n = 97;

Kết quả mong đợi:
long[] expected = new long[] {97};

Giải thích

No prime up to √97 ≈ 9.8 (2, 3, 5, 7) divides 97, so it is prime and the answer is [97].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Divide by 2 while you can, then move to 3, 5, 7, and so on.

Gợi ý 2

Shrink n each time you find a factor, and compare d × d with the shrunken n.

Gợi ý 3

If something greater than 1 is left after the loop, it is the largest prime factor.

Độ phức tạp mong đợi

O(√n) time, O(log n) extra space for the result

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.