القواسم والأعداد الأولية

الآن بعد أن عرفنا كيفية خلط الأعداد (GCD/LCM)، دعونا ننظر داخل عدد واحد.

نريد الإجابة على سؤالين كبيرين بكفاءة:

1. ما هي الأعداد التي تقسم \(N\)؟ (القواسم)
2. هل \(N\) عدد أولي؟

إذا كان \(N\) صغيراً (مثل 50)، فهذا سهل. إذا كان \(N\) هو 1,000,000,000، فإن القيام بذلك بالطريقة الخاطئة سيجمد الكود الخاص بك.

الفكرة الكبرى: تحسين الجذر التربيعي

هذه هي الحيلة الأكثر أهمية في نظرية الأعداد الأساسية.

إذا كنت تريد إيجاد عوامل 36، دعونا نسردها في أزواج:

• \(1 \times 36 = 36\)
• \(2 \times 18 = 36\)
• \(3 \times 12 = 36\)
• \(4 \times 9 = 36\)
• \(6 \times 6 = 36\) <– نقطة التحول (\(\sqrt{36}\))
• \(9 \times 4 = 36\) <– تكرار! رأينا {4, 9} بالفعل
• \(12 \times 3 = 36\) <– تكرار!
• \(18 \times 2 = 36\) <– تكرار!
• \(36 \times 1 = 36\) <– تكرار!

الاستنتاج: العوامل تأتي دائماً في أزواج. إذا كان \(a \times b = N\)، و \(a\) صغير، فإن \(b\) يجب أن يكون كبيراً. إنهما “يلتقيان” بالضبط عند \(\sqrt{N}\).

القاعدة: لا تحتاج أبداً للتحقق من الأعداد الأكبر من \(\sqrt{N}\). إذا لم تجد عاملاً بحلول ذلك الوقت، فإنه غير موجود (أو أنك وجدت شريكه بالفعل).

إيجاد القواسم

الهدف: اطبع جميع قواسم العدد \(N\).

الطريقة البطيئة

حلقة من 1 إلى \(N\). التعقيد: \(O(N)\)

// If N = 10^9, this takes ~10 second (too slow for many problems)
for (int i = 1; i <= n; i++) {
    if (n % i == 0) cout << i << " ";
}

الطريقة المحسّنة

حلقة من 1 إلى \(\sqrt{N}\). عندما تجد قاسماً \(i\)، فإنك تجد تلقائياً شريكه \(\frac{n}{i}\). التعقيد: \(O(\sqrt{N})\).

#include <iostream>
#include <vector>
#include <algorithm> // for sort
using namespace std;

int main() {
    long long n = 36;
    vector<long long> divisors;

    // Notice: i * i <= n is better than i <= sqrt(n)
    // It avoids slow floating-point math.
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i); // Add the small one
            
            // Add the big partner, but ONLY if they are different
            // (Check to avoid adding 6 twice for n=36)
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }

    // Note: The list won't be sorted (e.g., 1, 36, 2, 18...)

    for (long long d : divisors) cout << d << " ";
}

الأعداد الأولية

العدد الأولي هو عدد أكبر من \(1\) له بالضبط قاسمان: 1 ونفسه.

اختبار الأولية (هل \(N\) أولي؟)

باستخدام المنطق أعلاه: لإثبات أن عدداً أولي، نحتاج فقط للتحقق من أنه ليس لديه عوامل حتى \(\sqrt{N}\).

bool isPrime(long long n) {
    if (n <= 1) return false; // 0 and 1 are not prime
    
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false; // Found a divisor! Not prime.
        }
    }
    return true; // Survived the loop? It's prime.
}

أمثلة على المسائل

The Marching Band Formation

The Marching Band Formation

فرقة موسيقية في مدرسة ثانوية لديها 240 عضواً. مدير الفرقة يريد ترتيب الأعضاء في تشكيل مستطيل للموكب. ومع ذلك، هناك قيود محددة للتشكيل:

• يجب تضمين جميع الأعضاء في التشكيل.
• يجب أن يكون التشكيل مستطيلاً صلباً (بدون أماكن فارغة).
• يجب أن يكون هناك 10 صفوف على الأقل.
• لا يمكن أن يكون هناك أكثر من 20 صفاً.

كم عدد التشكيلات المستطيلة المختلفة التي تحقق هذه الشروط؟

Solution

لحل هذا، نحتاج لإيجاد قواسم 240. بما أننا نبحث عن أزواج (الصفوف \(\times\) الأعمدة = 240)، يمكننا استخدام طريقة الجذر التربيعي لإيجاد الأزواج بكفاءة.

int findDivisors(int n) {
    vector<pair<int, int>> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) {
                divisors.push_back({i, i});
            } else {
                divisors.push_back({i, n/i});
                divisors.push_back({n/i, i}); // Add both combinations of i and n/i
            }
        }
    }

    int count = 0;
    for (int i = 0; i < (int)divisors.size(); ++i){
        if (divisors[i].first >= 10 && divisors[i].first <= 20){
            count++;
        }
    }

    return count;
}

إذا كان \(N=240\)، تجد الدالة \(5\) حلول. هذه هي: - \(10\)، \(24\) - \(12\)، \(20\) - \(15\)، \(16\) - \(16\)، \(15\) - \(20\)، \(12\)

T-Prime

T-Prime

نعلم أن الأعداد الأولية هي أعداد صحيحة موجبة لها بالضبط قاسمان موجبان مختلفان. بالمثل، سنسمي عدداً صحيحاً موجباً \(t\) أولياً-T، إذا كان لـ \(t\) بالضبط ثلاثة قواسم موجبة مختلفة.

معطاة مصفوفة من \(n\) عدداً صحيحاً موجباً. لكل منهم حدد ما إذا كان أولياً-T أم لا.

Solution

يمكن إثبات أن مربعات الأعداد الأولية فقط هي أعداد T-أولية، وأنه لا يوجد الكثير منها. لماذا؟

إذا كان لدينا عاملان أوليان \(p\)، \(q\) لعدد \(t\)، فإنه سيكون قابلاً للقسمة على الأقل على \(p\)، \(q\)، \(pq\)، \(1\) - وهو أكثر من \(3\). إذن، يجب أن يكون قوة لعدد أولي. يمكنك أن ترى بسهولة الآن أن \(t = p\) أو \(t = p^3\) وأعلى، لا يعمل حقاً.

int n;
cin >> n;

for (int i = 0; i < n; ++i){
    int x;
    cin >> x;

    int y = sqrt(x);
    if (y * y != x){
        cout << "NO\n";
        continue; //check whether x is a perfect square
    }

    if (isPrime(y))
        cout << "YES\n";
    else
        cout << "NO\n"; 
}