التحليل إلى عوامل أولية

التحليل إلى عوامل أولية هو عملية تفكيك عدد إلى لبناته الأساسية (الأعداد الأولية).

وفقاً لـ المبرهنة الأساسية في الحساب، كل عدد صحيح \(>1\) له مجموعة فريدة من العوامل الأولية.

• \(12 = 2 \times 2 \times 3\) (أو \(2^2 \times 3\))
• \(100 = 2 \times 2 \times 5 \times 5\)
• \(13 = 13\) (أولي)

الطريقة 1: القسمة التجريبية (جيدة لـ \(N\) كبير)

إذا كان لديك عدد كبير (مثل \(10^{12}\))، نستخدم المنطق من درس “القواسم”. نكرر من \(2\) حتى \(\sqrt{N}\).

الخوارزمية: 1. ابدأ بـ \(d=2\). 2. طالما \(d\) يقسم \(N\)، استمر في قسمة \(N\) على \(d\) وسجل \(d\). 3. زد \(d\). 4. الخطوة الحاسمة: إذا بعد الحلقة \(N > 1\)، فإن \(N\) المتبقي هو عدد أولي بحد ذاته.

#include <iostream>
#include <vector>
using namespace std;

void factorize(long long n) {
    cout << "Factors of " << n << ": ";
    
    for (long long i = 2; i * i <= n; i++) {
        // While i divides n, it is a factor
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    
    // EDGE CASE: If n is still > 1, it is a prime factor
    if (n > 1) {
        cout << n;
    }
    cout << endl;
}

لماذا يعمل هذا؟

بحلول الوقت الذي نصل فيه إلى \(5\)، نكون قد قسمنا بالفعل جميع عوامل \(2\)، لذا لا يمكن أن يكون \(N\) قابلاً للقسمة على \(4\).

نقوم بتجريد العدد حتى يبقى العدد الأولي الأخير فقط.

التعقيد: \(O(\sqrt{N})\).

الطريقة 2: تحسين SPF (جيد للعديد من الاستعلامات)

إذا كنت بحاجة لتحليل 100,000 عدد (حيث كل عدد صغير، \(< 10^7\))، فإن الطريقة 1 بطيئة جداً.

يمكننا استخدام غربال معدل للتحليل في وقت لوغاريتمي (\(O(\log N)\)).

الفكرة: SPF (أصغر عامل أولي)

بدلاً من تخزين صحيح/خطأ في غربالنا، نخزن أصغر عامل أولي لكل عدد. - spf[10] = 2 - spf[15] = 3 - spf[7] = 7 (إنه أولي)

بمجرد حصولنا على هذه المصفوفة، يمكننا “القفز” إلى أسفل العدد فوراً. \(N \to N / spf[N] \to \dots \to 1\)

الحساب المسبق

const int MAXN = 1000000;
int spf[MAXN + 1];

void sieve() {
    // Initialize: smallest prime factor of i is i itself
    for (int i = 1; i <= MAXN; i++) spf[i] = i;

    for (int i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) { // If i is prime
            for (int j = i * i; j <= MAXN; j += i) {
                // Mark smallest factor for j if not marked yet
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

استعلام التحليل السريع

vector<int> getFactors(int x) {
    vector<int> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x = x / spf[x]; // Divide by smallest prime and continue
    }
    return ret;
}

التعقيد: \(O(\log N)\) لكل استعلام.

أيهما تستخدم؟

السيناريو	الطريقة	التعقيد
\(N\) ضخم (\(10^{12}\))	القسمة التجريبية	\(O(\sqrt{N})\)
استعلامات كثيرة، \(N\) صغير (\(10^7\))	SPF (الغربال)	\(O(\log N)\)
الذاكرة محدودة	القسمة التجريبية	\(O(1)\)

The Perfect Square Inventory

The Perfect Square Inventory

مدير مستودع تلقى شحنة من \(n\) صندوق تخزين مربع متطابق. يريد تكديسها على الأرض لتشكيل ترتيب مربع مثالي (مثلاً، \(10 \times 10\)، \(20 \times 20\)). ومع ذلك، أدرك أن \(n\) قد لا يكون عدداً مربعاً كاملاً، لذا لا يمكنه تشكيل مربع مع المخزون الحالي.

قرر طلب المزيد من الشحنات بنفس الحجم بالضبط (\(n\) صندوقاً لكل شحنة) حتى يسمح له العدد الإجمالي للصناديق ببناء مربع مثالي.

ما هو الحد الأدنى لعدد الشحنات (بما في ذلك الأولى) التي يحتاجها في المجموع؟

Solution

هذه مسألة تحليل لأننا نسأل: “بأي عدد صحيح \(k\) يجب أن نضرب \(n\) حتى تكون النتيجة مربعاً كاملاً؟”

عندما نحلل العدد إلى أعداد أولية، لكي نجعله مربعاً كاملاً، يجب أن يكون كل أس زوجياً. على سبيل المثال \(15 = 3^1 \cdot 5^1\)، يجب أن نضرب في \(3\cdot 5\) لجعل العدد \(225 = 3^2\cdot5^2\). من ناحية أخرى، العدد \(64 = 2^6\) هو بالفعل مربع كامل.

لذا في الأساس، لكل أس فردي يجب أن نضرب العدد بذلك العدد الأولي.

#include <iostream>
using namespace std;

// Function to find the smallest multiplier to make 'n' a perfect square
int findSmallestMultiplier(int n) {
    int multiplier = 1;

    // Step 1: Check for divisibility by 2
    int count = 0;
    while (n % 2 == 0) {
        count++;
        n /= 2;
    }
    // If the count of 2s is odd, we need one more 2 to make a pair
    if (count % 2 != 0) {
        multiplier *= 2;
    }

    // Step 2: Check for odd factors (3, 5, 7, ...)
    for (int i = 3; i * i <= n; i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n /= i;
        }
        // If the count of this factor is odd, we need one more to make a pair
        if (count % 2 != 0) {
            multiplier *= i;
        }
    }

    // Step 3: Handle the remaining prime number (if any)
    // If n > 2 at this point, the remaining n is a prime factor with a count of 1 (odd)
    if (n > 2) {
        multiplier *= n;
    }

    return multiplier;
}

int main() {
    int n;
    cin >> n;

    int necessary_shipments = findSmallestMultiplier(n);
    cout << necessary_shipments << "\n";

    return 0;
}

على سبيل المثال، لنفترض \(n = 540\). سيعيد الكود 15. دعونا نتحقق مما إذا كان هذا صحيحاً. \(540\cdot 15 =8100 = 90^2\). يمكننا أيضاً التأكد من أن هذا هو أصغر عدد من هذا القبيل عن طريق تجربة الأعداد الأصغر ورؤية أنها لا تعمل.