كيفية إيجاد العوامل الأولية (factors) لرقم

المطلوب : اكتب دالة تقوم بحساب عوامل أى رقم.

مثال : ما هي عوامل الرقم 20

الحل يمكن أن تقوم بعمل loop تبدأ من 1 إلى 20 تقوم بالتحقق من كل الأرقام من 1 إلى 20 وإذا كان الرقم يقسم 20 بدون باقي إذا هو عامل من عوامل ال 20 .

function printFactorsOfANumber(n: number): void {
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            console.log(i);
        }
    }
}

Time Complexity

لاحظ هنا أننا عندما نقسم 20 % 1 يكون الناتج صفر أى أن 1 يقسم 20 صحيحاً لأن 20 × 1 = 20

ثم نجرب ال 2 ونقول 20 % 2 يكون الناتج صفر أى أن 2 يقسم 20 صحيحاً لأن 10 × 2 = 20

ثم نجرب الثلاثة لا تص

ثم ال 4 فنقول 20 % 4 يكون الناتج صفر أى أن 4 تقسم ال 20 صحيحاً لأن 5 × 4 = 20

ثم ال 5 فنقول 20 % 5 يكون الناتج صفر أى أن 5 تقسم ال 20 صحيحاً لأن 4 × 5 = 20

لاحظ هنا أننا بدأنا نكرر العمليات وبعد ال 5 بإن ال 10 ستتكرر معنا لأن 2 × 10 = 10 وقد ممرنا سابقاً بالإثنين.

فنتسائل هنا حسناً يجب إذاً التحقق حتى نصل إلى رقم فيه تكرار ولكن كيف نعرف أن هذا الرقم الرقم الحرج الذي من بعده ستتكرر العوامل. والإجابة معروفه ستتكرر العوامل إذا قسمة الرقم بعد جذره التربيعي.

لاحظ أن الجذر التربيعي ل 20 هو 4.47 أى 4 إذا ما بعد الرقم 4 سيكون فيه تكرار وبالتالي سنتحقق من الأرقام من أول 1 حتى جذر الرقم التربيعي ونحسب ما يقسمه وما ناتج القسمة لنحصل على كل العوامل.

function printFactorsOfANumber2(n: number): void {
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            console.log(i);
            console.log(Math.floor(n / i));
        }
    }
}

ولكن هنا ستواجهنا مشكلة واحدة هو إذا كان الرقم مربع كامل مثل 36 فإن الدالة ستطبع عندما تصل إلى 6 ستطبع ال 6 مرتين لأن 6 × 6 = 36 والدالة تطبع ال i وهي 6 وتطبع أيضا n / i وهي 6 / 36 = 6 ولذلك يمكن أن نتحقق فقط إذا كان ناتج قسمة n / i == i فإننا نطبع الرقم مرة واحدة فقط وإلى فالدالة كما هي كالتالي:

function printFactorsOfANumber2(n: number): void {
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            if (Math.floor(n / i) === i) {
                console.log(i);
            } else {
                console.log(i);
                console.log(Math.floor(n / i));
            }
        }
    }
}

Time Complexity

ولكن هذه الدالة تطبع العوامل غير مرتبة مثلاً تطبع عوامل ال 20 كالتالي

1 20 2 10 4 5

وعوامل ال 36 كالتالي :

1 36 2 18 3 12 4 9 6

نلاحظ هنا أن ال (i) يتم طباعتها بالترتيب مثلاً في عوامل ال 36 ال (i) هي 1 2 3 4 6

وبالتالي نحن نريد أن نرتب فقط قيم (n / i) ونلاحظ أيضاً أن هذه القيم مرتبة ولكن مرتبة عكسياً فمثلاً في حالة ال 36 تكون قيمة (n / i) هي 36 18 12 9 ، وهنا يمكن ببساطة بدلاً من طباعة هذه القيمة مباشرة يمكن تخزينهم في مصفوفة ثم طباعتهم بالعكس كالتالي:

function printFactorsOfANumber2(n: number): void {
    let list: number[] = [];
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            if (Math.floor(n / i) === i) {
                console.log(i);
            } else {
                console.log(i);
                list.push(Math.floor(n / i))
            }
        }
    }
    for (let i = list.length - 1; i >= 0; i--) {
        console.log(list[i]);
    }
}

Time Complexity

Space complexity

إذا نحن هنا نستخم مساحة زيادة لطباعة العوامل بالترتيب.