عوامل عدد

Question

لديّ رقم أقل من 500،000،000 وأريد أن أضعه بطريقة فعالة. ما هي الخوارزمية التي تقترحها؟ ملاحظة: لدي حد زمني قدره 0.01 ثانية!

لقد كتبت للتو رمز C ++ هذا ولكنه فظيع للغاية!

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

وعلى نحو مضاعف شيء مثل هذا:

struct doubly
{
  int number;
  int power;
//and some functions!!

};

مجرد نقطة أخرى: أعرف أن n ليس رئيسًا

Answer 1

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

انظر إلى غربال إراتوستينيس. وربما تجد تلميحًا هذه الأسئلة والأجوبة؟ ماذا عن هذا?

إذا كنت ترغب في جعل هذا أسرع - بدون التجارة الكاملة في المكان/الوقت هذا الجواب - احسب جميع الأرقام الأولية حتى الجذر التربيعي البالغ 500،000،000 مقدما ووضعها في صفيف. من الواضح أن هذا يتم كسره عندما ينمو الحد الأعلى ؛)

Answer 2

ابدأ في دراسة الخوارزميات.
ما هي أسرع خوارزمية العوامل؟

Answer 3

عوامل جميع الأعداد الصحيحة تصل إلى 500،000،000 مقدما (لا يهم كيف) وتخزين العوامل في قاعدة بيانات أو تنسيق سجل ثابت. سيكون بحثك سريعًا ، ويجب أن تتناسب قاعدة البيانات على جهاز كمبيوتر حديث.

هذا هو أحد نهايات المقايضة/الفضاء ، لكنك لم تقل ما تحاول تحسينه.

بدلاً من ذلك ، انظر إلى الخوارزمية لـ GNU CoreUtils "عامل".

Answer 4

قد تجرب برسالة بولارد ، وهي مناسبة للأرقام المعقدة ذات المقسومات الصغيرة نسبيًا:

بولارد رو

Answer 5

إذا كانت هذه مهمة واجب منزلي ، أعتقد أنه يجب عليك إعادة قراءة مواد المحاضرة الخاصة بك.

على أي حال ، أنت تعرف أن رقمك مركب وصغير جدًا ، فهذا جيد.

بالنسبة لعملية تجريبية ساذجة مع جميع الأرقام ، تحتاج إلى اختبارات SQRT (500000000) على الأكثر-أي حوالي 22360 مرة لأسوأ حالة. من الواضح أنه يمكنك تخطي الأرقام الزوجية لأنها قابلة للقسمة باستخدام 2 (تحقق من ذلك أولاً). لذلك يصبح هذا 11180 أقسام لمدة 0.01 ثانية. إذا تمكن جهاز الكمبيوتر الخاص بك من القيام بـ 1.1 M أقسام في الثانية ، فيمكنك فقط استخدام النهج الساذج.

أو يمكنك عمل قائمة من الأعداد الأولية خارج الخط ، حتى SQRT (500 متر) ثم تجرب كل منها. هذا سوف يقلل من الانقسامات أكثر.

أو ، إذا لم تكن العوامل بعيدة جدًا عن بعضها البعض ، فيمكنك تجربة طريقة Fermat.

إذا لم تنجح هذه ، فيمكنك محاولة استخدام Pollard's Rho وغيرها.

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