كيف تجد كل العوامل الأولية في عدد صحيح طويل غير موقّع؟

Question

لدي مهمة للعثور على جميع العوامل الأولية للرقم ...

أحتاج إلى كتابة وظيفة تأخذ رقمًا وأخبرني جميع العوامل الأولية للرقم. علي سبيل المثال:

• ن = 350 العوامل الأولية: 2 5 5 7

(أنا مرر إلى الوظيفة رقم في النطاق من 0 إلى 18446744073709551615 - الحد الأقصى لعدد هو أكبر عدد يناسب عدد الأعداد الطويل الطويل غير موقعة 64 بت.)

Answer 1

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

على افتراض أن لديك حالة تافهة (على الأكثر) عامل رئيسي واحد كبير ، يمكنك تسريع بشكل كبير عن طريق القيام بشيء مثل العد من 2 ومحاولة كل رقم (عدة مرات إذا كان يعمل ؛ 12 سيكون 2 و 2 و 3 ل مثال). بعد العثور على عامل ، قلل من رقمك المستهدف بهذا العامل واختباره إذا كان الهدف الجديد هو Prime.

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

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

ومع ذلك ، فإن الشيء الرئيسي الذي يجب تذكره ، على الرغم من أن أكبر عامل ممكن لـ X ، إلى جانب X نفسه ، هو الجذر المربع لـ X. في كل مرة تجد فيها عاملًا ، فإن أكبر العامل المتبقي ممكنًا يتناقص بشكل كبير.