العامل الرئيسي من 300 000 000 000؟

Question

أحتاج إلى معرفة العوامل الرئيسية التي تزيد عن 300 مليار. لدي وظيفة تضيف إلى قائمةها ... ببطء شديد! لقد تم تشغيله لمدة ساعة تقريبًا الآن وأعتقد أنه حصل على مسافة عادلة للذهاب. هل أفعل ذلك خطأً كاملاً أم أن هذا متوقع؟

تحرير: أنا أحاول العثور على أكبر عامل رئيسي للرقم 600851475143.

تحرير: النتيجة:

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

Answer 1

هل تتذكر تقسيم الرقم الذي تعامله مع كل عامل كما تجدها؟

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

أنت الآن تبحث فقط عن عوامل 150 مليار. في كل مرة يجب أن تبدأ من العامل الذي وجدته للتو. لذلك إذا كان 2 عامل ، اختبار 2 مرة أخرى. إذا كان العامل التالي الذي تجده هو 3 ، فلا يوجد اختبار من 2 مرة أخرى.

وهلم جرا...

Answer 2

من الصعب العثور على العوامل الأولية باستخدام القوة الغاشمة ، والتي تبدو مثل التقنية التي تستخدمها.

فيما يلي بعض النصائح لتسريعها إلى حد ما:

• ابدأ منخفضًا وليس مرتفعًا
• لا تهتم باختبار كل عامل محتمل لمعرفة ما إذا كان الاختبار الرئيسي-مجرد اختبار محتمل للأعداد الأولية (الأرقام الفردية التي تنتهي في 1،3،7 أو 9)
• لا تهتم باختبار الأرقام الزوجية (كلها قابلة للقسمة على 2) ، أو الاحتمالات التي تنتهي في 5 (كلها قابلة للقسمة على 5). بالطبع ، لا تتخطى 2 و 5 !!
• عندما تجد عاملًا رئيسيًا ، تأكد من تقسيمه-لا تستمر في استخدام رقمك الأصلي الضخم. انظر مثالي أدناه.
• إذا وجدت عاملًا ، فتأكد من اختباره مرة أخرى لمعرفة ما إذا كان هناك عدة مرات. يمكن أن يكون رقمك 2x2x3x7x7x31 أو شيء من هذا القبيل.
• توقف عند الوصول> = SQRT (العدد الكبير المتبقي)

تحرير: مثال بسيط: أنت تجد عوامل 275.

1. اختبار 275 للقسمة بمقدار 2. هل 275/2 = int (275/2)؟ رقم فشل.
2. اختبار 275 للقسمة بمقدار 3. فشل.
3. تخطي 4!
4. اختبار 275 للقسمة بمقدار 5. نعم! 275/5 = 55. لذا فإن رقم الاختبار الجديد الخاص بك هو الآن 55.
5. اختبار 55 للقسمة بمقدار 5. نعم! 55/5 = 11. لذا فإن رقم الاختبار الجديد الخاص بك هو الآن 11.
6. ولكن 5> SQRT (11) ، لذلك 11 هو Prime ، ويمكنك التوقف!

لذلك 275 = 5 * 5 * 11

أكثر منطقية؟

Answer 3

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

بالنسبة لحل القوة الغاشمة ، تذكر أنه يمكنك القيام ببعض التحسينات المصغرة:

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

Answer 4

هنا حل XSLT!

هذا التحول XSLT يستغرق 0.109 ثانية.

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

ينتج هذا التحول النتيجة الصحيحة (الحد الأقصى للعامل الرئيسي البالغ 600851475143) في 0.109 ثانية فقط.:

6857

يستخدم التحول f:sqrt() و f:isPrime() المعرفة في FXSL 2.0 - مكتبة للبرمجة الوظيفية في XSLT. FXSL هو نفسه مكتوب تماما في XSLT.

f:isPrime() الاستخدامات نظرية فيرمات الصغيرة بحيث يكون من الفعال تحديد البدائية.

Answer 5

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

64 فقط لديه عامل رئيسي واحد ، 2. ستكتشف ذلك بشكل كبير إذا واصلت تقسيم 2 حتى لا يمكنك بعد الآن.

Answer 6

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

أنت تفعل شيئًا خاطئًا إذا استغرق الأمر ساعة. قد يكون لديك حتى حلقة لا حصر لها في مكان ما - تأكد من أنك لا تستخدم 32 بت ints.

Answer 7

مفتاح فهم سبب أهمية الجذر التربيعي ، ضع في اعتبارك أن كل عامل n أقل الجذر التربيعي لـ N له عامل مقابل في الاعلى هو - هي. لمعرفة ذلك ، ضع في اعتبارك أنه إذا كان x عامل n ، فإن x/n = m مما يعني أن x/m = n ، وبالتالي m هو أيضًا عامل.

Answer 8

لا أتوقع أن يستغرق الأمر وقتًا طويلاً على الإطلاق - هذا ليس عددًا كبيرًا بشكل خاص.

هل يمكن أن تعطينا رقمًا مثالًا يسبب صعوبات الكود الخاصة بك؟

Answer 9

إليك موقعًا واحدًا يمكنك الحصول على إجابات: Factoris - خدمة العوامل عبر الإنترنت. يمكن أن تفعل أعدادًا كبيرة حقًا ، ولكنها يمكن أن تعامل تعبيرات الجبرية.

Answer 10

أسرع الخوارزميات هي خوارزميات غربال ، وتستند إلى مناطق غامضة من الرياضيات المنفصلة (على رأسي على الأقل) ، معقدة في التنفيذ والاختبار.

إن أبسط خوارزمية للاحترام هي (كما قال آخرون) غربال إراتوستينيس. الأشياء التي يجب تذكرها حول استخدام هذا لعاملة رقم N:

• فكرة عامة: أنت تتحقق من سلسلة متزايدة من عوامل عدد صحيح محتملة x لمعرفة ما إذا كانوا يقسمون رقم المرشح بالتساوي N (في C/Java/JavaScript تحقق مما إذا كان N % x == 0) في هذه الحالة ، لا يكون N Prime.
• تحتاج فقط للذهاب إلى sqrt(N), ، لكن لا تحسب في الواقع sqrt(N): حلقة طالما أن عامل الاختبار X يمرر الاختبار x*x<N
• إذا كان لديك ذاكرة لحفظ مجموعة من الأعداد الأولية السابقة ، فاستخدم فقط تلك كعوامل الاختبار (ولا تنقذها إذا فشل Prime P في الاختبار P*P > N_max نظرًا لأنك لن تستخدمها مرة أخرى
• حتى لو لم تحفظ الأعداد الأولية السابقة ، للعوامل المحتملة x فقط تحقق 2 وجميع الأرقام الفردية. نعم ، سوف يستغرق الأمر وقتًا أطول ، ولكن ليس لفترة أطول بالنسبة للأرقام المعقولة الحجم. ال وظيفة التنازل الأولية ويمكن أن تخبرك التقريبي بما هو جزء من الأرقام. هذا الكسر يتناقص جداً ببطء. حتى ل 2⁶⁴ = حوالي 1.8x10¹⁹, ، ما يقرب من واحد من بين كل 43 رقمًا هو prime (= واحد من كل 21.5 أرقام فردية هو Prime). لعوامل الأرقام أقل من 2⁶⁴, تلك العوامل x أقل من 2³² حيث يكون حوالي واحد من كل 20 رقمًا هو prime = واحد من كل 10 أرقام فردية هو prime. لذلك سيتعين عليك اختبار 10 أضعاف عدد الأرقام ، ولكن يجب أن تكون الحلقة أسرع قليلاً ولا يتعين عليك العبث بتخزين كل هذه الأعداد الأولية.

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

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

Answer 11

قضيت بعض الوقت في هذا لأنه امتصني فقط. لن ألصق الكود هنا حتى الآن. بدلا من ذلك انظر هذه العوامل. gist إذا كنت فضوليا.

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

على جهاز MacBook الخاص بي ، يستغرق الأمر 0.002 ثانية لمحاكمة الرقم المذكور في السؤال (600851475143).

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

Answer 12

الرقم المحدد هو 300425737571؟ إنه عوامل تافهة إلى 131 * 151 * 673 * 22567. لا أرى ما هو كل هذا هو ...

Answer 13

إليكم بعض الخير يا رفاق :)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

استغرق الأمر حوالي 0.5 ثانية للعثور عليهم ، لذلك أسمي هذا النجاح.

Answer 14

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

Answer 15

تحتاج فقط إلى التحقق من أنه الباقي mod (n) حيث n هو prime <= sqrt (n) حيث n هو الرقم الذي تحاول عامله. لا ينبغي أن يستغرق الأمر أكثر من ساعة ، حتى على جهاز كمبيوتر بطيء حقًا أو Ti-85.

Answer 16

يجب أن تكون الخوارزمية الخاصة بك fubar. هذا لا يستغرق سوى حوالي 0.1s على Netbook 1.6 جيجاهرتز في بيثون. Python غير معروف بسرعة الحارقة. ومع ذلك ، لديها أعداد صحيحة دقة تعسفية ...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

(يبدو أن هذا الرمز يعمل في تحد لحقيقة أنني لا أعرف ما يكفي عن نظرية الأرقام لملء كشتبات.)

Answer 17

فقط للتوسع/التحسين قليلاً على "اختبار الأرقام الفردية فقط التي لا تنتهي في 5" اقتراحات ...

جميع الأعداد الأولية أكبر من 3 هي إما واحدة أو واحدة أقل من مضاعف 6 (6x + 1 أو 6x - 1 لقيم عدد صحيح من x).

Answer 18

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

أنت تقول أنك لا تريد حلولًا (؟) ، ولكن هنا تلميح "خفي". العوامل الأولية الوحيدة للعدد هي أدنى ثلاثة أعداد الأولية.

Answer 19

يتم استخدام الأرقام شبه الرائحة من هذا الحجم للتشفير ، لذلك أنا فضولي بشأن ما تريد بالضبط استخدامه له.

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