خوارزمية لحساب عدد المقسومات على رقم معين

Question

ما هي الخوارزمية الأمثل (من حيث الأداء) لحساب عدد المقسومات على رقم معين؟

سيكون أمرًا رائعًا أن تتمكن من تقديم كود زائف أو رابط لبعض الأمثلة.

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

Answer 1

ديمتري على حق في أنك تريد أن يقوم Sieve of Atkin بإنشاء القائمة الرئيسية ولكني لا أعتقد أن هذا سيهتم بالمشكلة برمتها.الآن بعد أن أصبحت لديك قائمة بالأعداد الأولية، ستحتاج إلى معرفة عدد هذه الأعداد الأولية التي تعمل كمقسوم عليها (وكم مرة).

إليك بعض لغة بايثون للخوارزمية انظر هنا وابحث عن "الموضوع:الرياضيات - تحتاج إلى خوارزمية المقسومات".ما عليك سوى حساب عدد العناصر الموجودة في القائمة بدلاً من إعادتها.

وهنا د.الرياضيات وهذا ما يفسر بالضبط ما عليك القيام به رياضيا.

في الأساس يتلخص الأمر في ما إذا كان رقمك n يكون:
n = a^x * b^y * c^z
(حيث A و B و C هي المقسومات الرئيسية لـ N و X و Y و Z هي عدد المرات التي يتكرر فيها المقسوم) ثم العدد الكلي لجميع المقسومات هو:
(x + 1) * (y + 1) * (z + 1).

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

لست متأكدًا بنسبة 100٪ من وصف الخوارزمية الخاص بي، ولكن إذا لم يكن الأمر كذلك فهو شيء مشابه.

Answer 2

هناك كثير تقنيات أكثر للتخصيم من غربال أتكين.على سبيل المثال، لنفترض أننا نريد تحليل الرقم 5893.حسنا، الجذر التربيعي له هو 76.76 ...الآن سنحاول كتابة 5893 كحاصل ضرب المربعات.حسنًا (77*77 - 5893) = 36 وهو ما يساوي 6 تربيع، إذن 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71.إذا لم ينجح ذلك، لكنا قد نظرنا فيما إذا كان 78*78 - 5893 مربعًا كاملاً.وما إلى ذلك وهلم جرا.باستخدام هذه التقنية، يمكنك اختبار العوامل القريبة من الجذر التربيعي لـ n بشكل أسرع بكثير من اختبار الأعداد الأولية الفردية.إذا قمت بدمج هذه التقنية لاستبعاد الأعداد الأولية الكبيرة مع المنخل، فسيكون لديك طريقة تحليل أفضل بكثير من المنخل وحده.

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

لذلك، ما لم تكن تتعامل مع أعداد صحيحة صغيرة، فلن أحاول حل هذه المشكلة بنفسي.بدلاً من ذلك سأحاول إيجاد طريقة لاستخدام شيء مثل باري مكتبة لديها بالفعل حل عالي الكفاءة تم تنفيذه.وبهذا يمكنني تحليل رقم عشوائي مكون من 40 رقمًا مثل 124321342332143213122323434312213424231341 في حوالي 0.05 ثانية.(تحليلها، في حال كنت تتساءل، هو 29*439*1321*157907*284749*33843676813*4857795469949.أنا واثق تمامًا من أنه لم يتم اكتشاف ذلك باستخدام منخل أتكين...)

Answer 3

@ ياسكي

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

يحاول:

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

Answer 4

أنا لا أوافق على أن غربال أتكين هو الحل الأمثل، لأنه قد يستغرق وقتًا أطول للتحقق من كل رقم في [1,n] بحثًا عن الأولية مقارنة بتقليل العدد عن طريق القسمة.

إليك بعض التعليمات البرمجية التي، على الرغم من أنها أكثر اختراقًا قليلاً، إلا أنها أسرع بكثير بشكل عام:

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ملاحظة هذا كود بايثون يعمل لحل هذه المشكلة.

Answer 5

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

1 بالنظر إلى N، ابحث عن القائمة L للعوامل الأولية لـ N

2 بالنظر إلى L، احسب عدد المجموعات الفريدة

تشير جميع الإجابات التي أراها حتى الآن إلى رقم 1 وتفشل في الإشارة إلى أنها غير قابلة للتتبع بالنسبة لأعداد هائلة.بالنسبة لأرقام N متوسطة الحجم، وحتى أرقام 64 بت، يكون الأمر سهلاً؛بالنسبة إلى N الهائلة، يمكن أن تستغرق مشكلة التخصيم "إلى الأبد".يعتمد تشفير المفتاح العام على هذا.

السؤال رقم 2 يحتاج إلى مزيد من المناقشة.إذا كان L يحتوي على أرقام فريدة فقط، فهي عملية حسابية بسيطة باستخدام الصيغة المركبة لاختيار كائنات k من عناصر n.في الواقع، أنت بحاجة إلى جمع النتائج من تطبيق الصيغة مع تغيير k من 1 إلى sizeof(L).ومع ذلك، عادةً ما يحتوي L على تكرارات متعددة للأعداد الأولية المتعددة.على سبيل المثال، L = {2,2,2,3,3,5} هو تحليل N = 360.الآن هذه المشكلة صعبة للغاية!

إعادة صياغة رقم 2، نظرًا لأن المجموعة C تحتوي على عناصر k، مثل هذا العنصر أ يحتوي على "مكررات"، والعنصر ب يحتوي على "ب" مكررات، وما إلى ذلك.كم عدد المجموعات الفريدة من العناصر من 1 إلى k-1 الموجودة؟على سبيل المثال، {2}، {2,2}، {2,2,2}، {2,3}، {2,2,3,3} يجب أن يحدث كل منها مرة واحدة ومرة ​​واحدة فقط إذا كان L = {2,2 ،2،3،3،5}.كل مجموعة فرعية فريدة من نوعها هي مقسوم فريد على N عن طريق ضرب العناصر الموجودة في المجموعة الفرعية.

Answer 6

تعتمد الإجابة على سؤالك بشكل كبير على حجم العدد الصحيح.طرق الأعداد الصغيرة، على سبيل المثالأقل من 100 بت، وبالنسبة للأرقام ~ 1000 بت (مثل المستخدمة في التشفير) فهي مختلفة تمامًا.

• لمحة عامة: http://en.wikipedia.org/wiki/Divisor_function

• القيم الصغيرة n و بعض المراجع المفيدة: A000005:d(n) (وتسمى أيضًا tau(n) أو sigma_0(n)))، عدد مقسومات n.

• مثال من العالم الحقيقي: تحليل الأعداد الصحيحة

Answer 7

فيما يلي خوارزمية O(sqrt(n)) المباشرة للأمام.لقد استخدمت هذا لحل مشروع أويلر

def divisors(n):
    count=2 # accounts for 'n' and '1'
    i=2
    while(i**2 < n):
        if(n%i==0):
            count+=2
        i+=1
    count+=(1 if i**2==n else 0)
    return count  

Answer 8

سطر واحد فقط
لقد فكرت في حذرة للغاية بشأن سؤالك وحاولت كتابة قطعة رمز عالية الكفاءة وأداء لطباعة جميع المقسومات من رقم معين على الشاشة ، نحتاج فقط إلى سطر واحد من التعليمات البرمجية!(استخدم الخيار -std=c99 أثناء التجميع عبر دول مجلس التعاون الخليجي)

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

للعثور على أعداد المقسومات، يمكنك استخدام الوظيفة التالية السريعة جدًا (تعمل بشكل صحيح مع جميع الأعداد الصحيحة باستثناء 1 و 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

أو إذا تعاملت مع رقم معين كمقسوم عليه (العمل بشكل صحيح مع كل الأعداد الصحيحة باستثناء 1 و 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

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

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

أو

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

الصغير جميل :)

Answer 9

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

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

الخطوات الأساسية لحساب المقسومات على الرقم (n) هي [هذا كود زائف تم تحويله من كود حقيقي لذا آمل ألا أكون قد أدخلت أخطاء]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

Answer 10

قد تحاول هذا واحد.إنه اختراق بعض الشيء، لكنه سريع إلى حد معقول.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

Answer 11

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

على سبيل المثال:36 العوامل الأولية:2^2*3^2 المقسومات:1 ، 2 ، 3 ، 4 ، 6 ، 9 ، 12 ، 18 ، 36 عدد المقسومات:9

أضف واحدًا إلى كل أسس 2^3*3^3 الضاعفة:3*3 = 9

Answer 12

قبل أن تلتزم بحل، ضع في اعتبارك أن أسلوب الغربال قد لا يكون إجابة جيدة في الحالة النموذجية.

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

1) على الرغم من أن الإنسان يستغرق بعض الوقت لإجراء عملية القسمة، إلا أنه سريع جدًا على الكمبيوتر - وهو ما يشبه تكلفة البحث عن الإجابة.

2) إذا لم يكن لديك جدول أولي، فيمكنك إنشاء حلقة يتم تشغيلها بالكامل في ذاكرة التخزين المؤقت L1.وهذا يجعلها أسرع.

Answer 13

هذا حل فعال:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}

Answer 14

المقسومون يفعلون شيئًا مذهلاً:ينقسمون تماما.إذا كنت تريد التحقق من عدد المقسومات على رقم ما، n, ، فمن الواضح أنه زائد عن الحاجة ليشمل النطاق بأكمله، 1...n.لم أقم بإجراء أي بحث متعمق لهذا الأمر ولكني قمت بحلها مسألة مشروع أويلر 12 على الأعداد المثلثية.الحل الخاص بي ل أكبر من 500 المقسوم عليه تم تشغيل الاختبار لمدة 309504 ميكروثانية (~0.3 ثانية).لقد كتبت وظيفة المقسوم على الحل.

int divisors (int x) {
    int limit = x;
    int numberOfDivisors = 1;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            numberOfDivisors++;
        }
    }

    return numberOfDivisors * 2;
}

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

اجازة سعيدة.

Answer 15

تريد غربال أتكين الموصوف هنا: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Answer 16

طريقة الأعداد الأولية واضحة جدًا هنا.P[] هي قائمة بأعداد أولية أقل من أو تساوي sq = sqrt(n) ؛

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .

Answer 17

تسمي الكتب المدرسية لنظرية الأعداد دالة عد المقسوم عليه تاو.الحقيقة الأولى المثيرة للاهتمام هي أنها متضاعفة، أي.τ(ab) = τ(a)τ(b) ، عندما لا يكون لـ a و b عامل مشترك.(دليل:كل زوج من المقسومات على a وb يعطي مقسومًا مميزًا على ab).

لاحظ الآن أنه بالنسبة لـ p عدد أولي، τ(p**k) = k+1 (قوى p).وبالتالي يمكنك بسهولة حساب τ(n) من عواملها.

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

1. اختبار ما إذا كان الرقم أوليًا (سريعًا)
2. إذا كان الأمر كذلك، ارجع 2
3. خلاف ذلك، تحليل الرقم (بطيئة إذا كانت هناك عوامل أولية كبيرة متعددة)
4. احسب τ(n) من التحليل

Answer 18

فيما يلي برنامج C للعثور على عدد المقسومات على رقم معين.

تعقيد الخوارزمية المذكورة أعلاه هو O(sqrt(n)).

ستعمل هذه الخوارزمية بشكل صحيح مع الأرقام التي تعتبر مربعة كاملة وكذلك الأرقام التي ليست مربعة كاملة.

لاحظ أنه تم تعيين الحد الأعلى للحلقة على الجذر التربيعي للرقم لجعل الخوارزمية أكثر كفاءة.

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

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

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

for(i=2;i*i<=n;i++)
{
    ...
}

Answer 19

هذه هي الوظيفة التي كتبتها.إنه أسوأ تعقيد زمني هو O(sqrt(n))، وأفضل وقت من ناحية أخرى هو O(log(n)).فهو يوفر لك جميع المقسومات الأولية بالإضافة إلى عدد حدوثها.

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}

Answer 20

هذه هي الطريقة الأساسية لحساب مقسومات الأرقام:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}

Answer 21

@ كيندال

لقد اختبرت الكود الخاص بك وأجريت بعض التحسينات، والآن أصبح الأمر أسرع.لقد اختبرت أيضًا كود @هومن جاویدپور، وهذا أيضًا أسرع من الكود الخاص به.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}

Answer 22

أليست هذه مجرد مسألة تحليل الرقم إلى عوامله - تحديد جميع عوامل الرقم؟يمكنك بعد ذلك أن تقرر ما إذا كنت بحاجة إلى كل المجموعات المكونة من عامل واحد أو أكثر.

لذلك، إحدى الخوارزميات المحتملة ستكون:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

والأمر متروك لك بعد ذلك لدمج العوامل لتحديد بقية الإجابة.

Answer 23

هذا شيء توصلت إليه بناءً على إجابة جاستن.قد يتطلب الأمر بعض التحسين.

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))

Answer 24

أعتقد أن هذا هو ما تبحث عنه. سأفعل بالضبط ما طلبته.انسخها والصقه في "المفكرة". احفظ باسم *.bat.Run. أدخل الرقم. اضرب العملية بـ 2 وهذا هو عدد المقسومات. لقد قمت بذلك عن قصد حتى تحدد المقسومات بشكل أسرع:

يرجى ملاحظة أن متغير CMD غير قادر على دعم القيم التي تزيد عن 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start

Answer 25

أعتقد أن هذا سيكون مفيدًا ودقيقًا

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Answer 26

جرب شيئًا على هذا المنوال:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}

Answer 27

يمكنك حساب الأعداد الأولية مسبقًا حتى الجذر التربيعي لأقصى عدد ممكن من N وحساب أس كل عامل أولي لرقم ما.عدد قواسم n (n = p1^a p2^b p3^c...) هو (a+1)(b+1)(c+1) لأنها نفس طريقة حساب العدد الأولي أعداد هذه العوامل (وهذا سيحسب عدد المقسومات).هذا سريع جدًا إذا قمت بحساب الأعداد الأولية مسبقًا

معلومات أكثر تفصيلاً عن هذه الطريقة:

https://mathschallenge.net/library/number/number_of_divisors

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

http://primes.utm.edu/glossary/xpage/tau.html

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int divisors_count(const vector<int>& primes, int n)
{
    int divisors = 1;
    for (int i = 0; i < primes.size(); ++i) {
        int factor = primes[i];
        int factor_exponent = 0;
        while (n % factor == 0) {
            ++factor_exponent;
            n /= factor;
        }
        divisors *= (factor_exponent + 1);
    }
    if (n > 1) 
        return 2*divisors; // prime factor > sqrt(MAX_N)
    return divisors;
}

int main()
{
    const int MAX_N = 1e6;
    int max_factor = sqrt(MAX_N);

    vector<char> prime(max_factor + 1, true);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            for (int j = 3*i; j <= max_factor; j += 2*i) {
                prime[j] = false;
            }   
        }
    }

    vector<int> primes;
    primes.reserve(max_factor/2);
    primes.push_back(2);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            primes.push_back(i);
        }
    }

    int n;
    while (cin >> n) {
        cout << divisors_count(primes, n) << endl;
    }
}

Answer 28

لا أعرف الطريقة الأكثر فعالية، لكني سأفعل ما يلي:

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

يجب أن تعمل \o/

إذا كنت بحاجة، يمكنني برمجة شيء ما غدًا بلغة C للتوضيح.