مشاكل مع الأعداد الرئيسية

Question

أحاول كتابة برنامج للعثور على أكبر عامل رئيسي لعدد كبير جدا، وقد جربت عدة طرق نجاح متفاوتة. كل تلك التي وجدتها حتى الآن كانت بطيئة بشكل لا يصدق. كان لدي فكر، وأتساءل عما إذا كان هذا نهج صالح:

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

هذا النهج سوف يستغرق مدخلات، وسوف تفعل ما يلي:

200 -> 100 -> 50 -> 25 -> 5 (العودة)

90 -> 45 -> 15 -> 5 (العودة)

يقسم CurrentNum مرارا وتكرارا من قبل أصغر عدد قابل للقسمة (في أغلب الأحيان 2، أو 3) حتى يأتي جيارا نفسها (لا يوجد رقم رئيسي قابل للقسائم أقل من Squareroot من CurrentNum)، وفترض أن هذا هو أكبر عامل رئيسي في المدخلات الأصلية.

هل سيعمل هذا دائما؟ إذا لم يكن كذلك، هل يمكن لشخص أن يعطيني مثال مضاد؟

-

تحرير: بحجم كبير جدا، أقصد حوالي 2 ^ 40، أو 10 ^ 11.

Answer 1

هذا سوف يعمل دائما بسبب نظرية فريدة من نوعها نوريم.

Answer 2

سوف تعمل الطريقة، ولكنها ستكون بطيئة. "ما حجم أرقامك؟" يحدد الطريقة المراد استخدامها:

• أقل من 2 ^ 16 أو نحو ذلك: طاولة البحث.
• أقل من 2 ^ 70 أو نحو ذلك: غربال اتكين. وبعد هذه نسخة محسنة من أكثر المعروفة غربال eratosthenes.. يحرر: تعديل ريتشارد برنت من خوارزمية بولارد قد يكون أفضل في هذه الحالة.
• أقل من 10 ^ 50: Lenstra Illiptic منحنى التعامل مع
• أقل من 10 ^ 100: الغربال التربيعي
• أكثر من 10 ^ 100: الحقل رقم عام

Answer 3

بالتأكيد سيعمل (انظر جواب مارك BYERS)، ولكن بالنسبة للمدخلات "كبيرة جدا" قد يستغرق وقتا طويلا. يجب أن تلاحظ أن مكالمتك إلى getLowestDivisiblePrimeNumber() يخفي حلقة أخرى، لذلك يعمل هذا في O (n ^ 2)، وهذا اعتمادا على ما تقصده "كبير جدا" قد تضطر إلى العمل برعاية التي ستكون بطيئة.

يمكنك تسريعها قليلا، من خلال الإشارة إلى أن الخوارزمية الخاصة بك لا تحتاج أبدا إلى عدم التحقق من العوامل أصغر من آخر وجدت.

Answer 4

أنت تحاول العثور على العوامل الرئيسية من عدد. إن ما تقترحه ستعمل، ولكنه سيظل بطيئا للأعداد الكبيرة .... يجب أن تكون شاكرا لهذا الغرض، لأن معظم الأمن الحديث يتعرضن لهذه مشكلة صعبة.

Answer 5

من بحث سريع، أنا فقط فعلت، أسرع طريقة معروفة لعامل رقم هو باستخدام طريقة منحنى الإهليلجية.

يمكنك محاولة رمي رقمك في هذا العرض التوضيحي: http://www.alpertron.com.ar/ecm.htm. .

إذا أقنعك ذلك، فيمكنك أن تحاول سرقة الكود (هذا ليس متعة، فهي توفر رابطا به!) أو قراءة حول نظرية ذلك في أي مكان آخر. هناك مقال ويكيبيديا حول هذا الموضوع هنا: http://en.wikipedia.org/wiki/lenstra_elliptic_curve_factorization. لكنني أغبي جدا لفهمه. لحسن الحظ، إنها مشكلتك، وليس لي! :)

Answer 6

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

طريقة واحدة يمكنك حل هذه المشكلة هي استخدام حلقة تجد دائما أصغر عامل (عدد صحيح موجب) لعدد. عندما يكون أصغر عامل رقم رقم هذا الرقم، ثم وجدت أكبر عامل رئيسي!

خوارزمية مفصلة الوصف:

يمكنك القيام بذلك عن طريق إبقاء ثلاثة متغيرات:

الرقم الذي تحاول عامله (أ) محل محمي (ب) أكبر متجر مقسوم (ج)

في البداية، دع (أ) يكون الرقم الذي تهتم به - في هذه الحالة، هو 600851475143. ثم اسمحوا (ب) يكون 2. لديك مشروط شيكات إذا كان (أ) قابل للقسمة (ب). إذا كانت قساءة قساءة، فقسمة (أ) بواسطة (b)، إعادة تعيين (B) إلى 2، والعودة إلى التحقق من ذلك إذا (أ) قابل للقسمة (ب). آخر، إذا كان (أ) غير قابل للقسمة بواسطة (B)، وزيادة (B) بواسطة +1 ثم تحقق مما إذا كان (أ) قابل للقسمة بواسطة (B). قم بتشغيل الحلقة حتى (أ) هو 1. (3) سوف تكون أكبر مقسوم رئيسي 600851475143.

هناك العديد من الطرق التي يمكن أن تجعل هذا أكثر فعالية - بدلا من زيادة عدد صحيح القادم، يمكنك زيادة عدد صحيح رئيسي للضرورة، وبدلا من الحفاظ على أكبر متجر مقسوم، يمكنك فقط إرجاع الرقم الحالي عند مقسمه الوحيد بحد ذاتها. ومع ذلك، فإن الخوارزمية التي وصفتها أعلاه سيتم تشغيلها في ثوان بغض النظر.

التنفيذ في بيثون على النحو التالي: -

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

مثال: لنجد أكبر عامل رئيسي 105 باستخدام الطريقة الموضحة أعلاه.

دع (أ) = 105. (ب) = 2 (نبدأ دائما مع 2)، وليس لدينا قيمة ل (ج) حتى الآن.

هل (أ) قابل للقسمة بواسطة (ب)؟ رقم الزيادة (ب) بواسطة +1: (ب) = 3. هو (أ) قابل للقسمة بواسطة (ب)؟ نعم. (105/3 = 35). تم العثور على أكبر مقسم الآن حتى الآن هو 3. السماح (ج) = 3. التحديث (A) = 35. إعادة تعيين (B) = 2.

الآن، هل (أ) قساءة من قبل (ب)؟ رقم الزيادة (ب) حسب +1: (ب) = 3. (أ) قابل للقسمة بواسطة (ب)؟ رقم الزيادة (ب) حسب +1: (ب) = 4. (أ) قابل للقسمة بواسطة (ب)؟ رقم الزيادة (ب) بواسطة +1: (ب) = 5. (أ) قابل للقسمة بواسطة (ب)؟ نعم. (35/5 = 7). أكبر مقسم وجدنا سابقا يتم تخزينه في (ج). (ج) هو حاليا 3. 5 أكبر من 3، لذلك نحن نقوم بتحديث (C) = 5. نقوم بتحديث (أ) = 7. نشدد (ب) = 2.

ثم نكرر عملية (أ)، لكننا سوف نستمر فقط بزيادة (ب) حتى (ب) = (أ) = (أ)، لأن 7 هو رئيس الوزراء وليس له أي دفاتر غير نفسه و 1. (يمكننا أن نتوقف بالفعل متى (ب )> ((أ) / 2)، لأنك لا تستطيع أن يكون لديك طبيب عدد صحيح أكبر من نصف عدد - أصغر مقسيم ممكن (بخلاف 1) من أي رقم هو 2!)

لذلك في تلك المرحلة نعود (أ) = 7.

حاول القيام ببعض هذه باليد، وستحصل على تعليق الفكرة