توليد جميع عوامل الرقم بالنظر إلى عامله الرئيسي

Question

إذا كان لديك بالفعل العوامل الأولية لعدد ، فما هي أسهل طريقة للحصول على مجموعة من جميع عوامل هذا الرقم؟ أعلم أنه يمكنني مجرد حلقة من 2 إلى SQRT (N) وأجد جميع الأرقام القابلة للقسمة ، لكن هذا يبدو غير فعال لأن لدينا بالفعل العوامل الأولية.

أتصور أنها في الأساس نسخة معدلة من الوظائف / الاختيار ، ولكن كل ما يمكن أن أجده هو طرق حساب عدد المجموعات ، وطرق حساب عدد العوامل ، وليس لإنشاء المجموعات / العوامل بالفعل.

Answer 1

تخيل المقسومات الرئيسية هي الكرات في دلو. على سبيل المثال ، إذا كانت المقسومات الأولية لرقمك هي 2 أو 2 و 2 و 3 و 7 ، فيمكنك أخذ مثيلات 0 أو 1 أو 2 أو 3 من "الكرة 2". وبالمثل ، يمكنك أخذ "الكرة 3" 0 أو 1 مرات و "الكرة 7" 0 أو 1 مرات.

الآن ، إذا أخذت "Ball 2" مرتين و "الكرة 7" مرة واحدة ، ستحصل على المقسوم 2*2*7 = 28. وبالمثل ، إذا لم تأخذ كرات ، فستحصل *2*2*3*7 الذي يساوي الرقم نفسه.

وأخيراً ، للحصول على جميع المجموعات الممكنة من الكرات التي يمكنك تناولها من الدلو ، يمكنك بسهولة استخدام العودية.

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

الآن يمكنك تشغيله على مثال أعلاه:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);

Answer 2

DIMO414 ، تعتبر عوامل توليد عمومًا مهمة صعبة للغاية. في الواقع ، فإن حماية معظم أصولك المهمة (أي المال والمعلومات. ، إلخ) ، تعتمد على المهمة البسيطة ، ولكنها صعبة للغاية في تحقيق رقم. انظر هذا المقال عن مخطط تشفير RSA http://en.wikipedia.org/wiki/rsa_(cryptosystem). أنا أستطرد.

للإجابة على سؤالك ، فإن النهج التوافقي هو أفضل طريقة لك كما أشارت نيكيتا (راجع للشغل ، مجد على شرحك).

أعلم أنه يمكنني فقط حلقة من 2 إلى SQRT (N) والعثور على جميع الأرقام القابلة للقسمة

كثير من الناس يقفزون إلى هذا الاستنتاج بسبب المفهوم المشابه للغاية المرتبط بتوليد الأعداد الأولية. لسوء الحظ ، هذا غير صحيح ، حيث ستفتقد عدة عوامل أكبر من SQRT (N) التي ليست أعدادًا رئيسية (سأسمح لك بإثبات ذلك لنفسك).

الآن ، لتحديد عدد العوامل لأي رقم معين n ، نتطلع إلى العوامل الأولية ن. إذا ن = ص^أ, ، ثم نعلم أن N سيكون (A + 1) عوامل (1 ، ص ، ص², ، ... ، ص^أ). هذا هو المفتاح لتحديد العدد الإجمالي للعوامل. إذا ن كان لديه العديد من العوامل الأولية ، على سبيل المثال

ن = ص₁^أ· ص₂^ب··· ص_ك^ص

ثم باستخدام سيادة المنتج من العد (http://en.wikipedia.org/wiki/rule_of_product) ، نحن نعلم أنه سيكون هناك

م = (A + 1)·(ب + 1)···(R + 1)

عوامل. الآن ، كل ما نحتاج إلى القيام به هو العثور على كل مجموعة ممكنة من الأرقام التي قدمها لنا العوامل الأولية. فيما يلي بعض التعليمات البرمجية في R ، والتي نأمل أن توضح ما شرحت.

يقوم الجزء الأول من الكود الخاص بي بفحص بسيط من البدائية لأنه إذا كان الرقم أولي ، فإن العوامل الوحيدة هي 1 وحد ذاتها. بعد ذلك ، إذا لم يكن الرقم رئيسيًا وأكبر من 1 ، فأنا أجد أولاً العوامل الأولية للرقم ، قلنا ، لدينا ،

ن = ص₁^أ· ص₂^ب··· ص_ك^ص

بعد ذلك أجد فقط الأعداد الأولية الفريدة uniprimes ، لذلك على سبيل المثال ، سوف تحتوي uniprimes (ص₁, ، ص₂, ، ص_ك). ثم أجد جميع صلاحيات كل برايم وأضفها إلى صفيف MyFactors. بعد صنع هذه المجموعة ، أجد كل مجموعة منتجات ممكنة من العناصر في MyFactors. أخيرًا ، أضيف 1 إلى الصفيف (لأنه عامل تافهة) ، وفرزه. هاهو! إنه سريع للغاية ويعمل لأعداد كبيرة جدًا مع العديد من العوامل.

حاولت أن أجعل الكود قابل للترجمة قدر الإمكان إلى لغات أخرى (أي أفترض أنك قمت بالفعل ببناء وظيفة تولد العوامل الأولية (أو باستخدام وظيفة مدمجة) ووظيفة اختبار العدد الأولية.) ولم أفعل ذلك T استخدم وظائف مدمجة متخصصة فريدة من نوعها لـ R. اسمحوا لي أن أعرف ما إذا كان هناك شيء غير واضح. هتافات!

factor2 <- function(MyN) {

    CheckPrime <- isPrime(MyN)

    if (CheckPrime == F && !(MyN == 1)) {
            MyPrimes <- primeFactors(MyN)
            MyFactors <- vector()
            MyPowers <- vector()
            UniPrimes <- unique(MyPrimes)
                    for (i in 1:length(UniPrimes)) {

                            TempSize <- length(which(MyPrimes == UniPrimes[i]))

                            for (j in 1:TempSize) {
                                    temp <- UniPrimes[i]^j
                                    MyPowers <- c(MyPowers, temp)
                            }

                    }
            MyFactors <- c(MyFactors, MyPowers)
            MyTemp <- MyPowers
            MyTemp2 <- vector()
            r <- 2
            while (r <= length(UniPrimes)) {

                    i <- 1L

                    while (i <= length(MyTemp)) {
                            a <- which(MyPrimes >  max(primeFactors(MyTemp[i])))
                                    for (j in a) {
                                            temp <- MyTemp[i]*MyPowers[j]
                                            MyFactors <- c(MyFactors, temp)
                                            MyTemp2 <- c(MyTemp2, temp)
                                    }
                            i <- i + 1
                    }
                    MyTemp <- MyTemp2
                    MyTemp2 <- vector()
                    r <- r + 1
            }
    } else {
            if (MyN == 1) {
                    MyFactors <- vector()
            } else {
                    MyFactors <- MyN
            }
    }
    MyFactors <- c(1, MyFactors)
    sort(MyFactors)
}