मध्यम 0 हल किए गए 0% स्वीकृति

Prime Factorization

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

आप क्या सीखेंगे

  • 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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

1 ≤ n ≤ 10^12

उदाहरण

उदाहरण 1
इनपुट:
n = 360

अपेक्षित आउटपुट:
expected = [2, 2, 2, 3, 3, 5]
इनपुट:
long long n = 360;

अपेक्षित आउटपुट:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
इनपुट:
long n = 360;

अपेक्षित आउटपुट:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

व्याख्या

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].

उदाहरण 2
इनपुट:
n = 97

अपेक्षित आउटपुट:
expected = [97]
इनपुट:
long long n = 97;

अपेक्षित आउटपुट:
std::vector<long long> expected = {97};
इनपुट:
long n = 97;

अपेक्षित आउटपुट:
long[] expected = new long[] {97};

व्याख्या

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

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।