• 0
Khaled Alshaya

هل هناك طريقة لمعرفة عدد قواسم عدد ما ؟

سؤال

في الحقيقة أني أعيش جو الإجازة حالياً و لكن واجهني سؤال على الانترنت عقدني قليلاً :lol:

السؤال ببساطة عبارة عن برنامج, هذا البرنامج تعطيه عدد ما و ناتجه يعطيك عدد قواسم ذلك العدد.

مثلاً العدد 15 قواسمه الصحيحة هي 1, 3, 5, 15 بالتالي عدد قواسم العدد 15 هو 4 قواسم.

ببرنامج بسيط أستطيع فحص قواسم أي عدد, و لكن المشكلة تظهر أنني أريد معرفة قواسم أعداد "كبيرة جداً" و ليس عدداً واحداً بل عدداً غير معروف من الأعداد,

فمثلاً أريد معرفة أصغر عدد عدد قواسمه أكثر من مئة و هكذا, أرجو أن تكون الفكرة قد اتضحت,

ما أريد فهمه هو هل توجد طريقة لمعرفة "عدد" تلك القواسم حتى لو لم نعرف ما هي تلك القواسم,

قرأت هذه الصفحة و لكني لم أفهم شيئاً :blush:

Divisor function

هل هناك من يبسط لنا الموضوع :)

عمل brute force في حالتي لايجدي نفعاً على حاسوبي الشخصي :lol:,

تحياتي ,,

تم تعديل بواسطه Khaled.Alshaya
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

12 إجابة على هذا السؤال .

  • 0

بشكل عام:

ليكن m عددا صحيحا طبيعيا، إذن يمكن تفكيك هذا العدد إلى جداء عوامل أولية:

:)
تم تعديل بواسطه caballero
خطأ إملائي
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ,,

شكراً جزيلاً caballero :)

أعتقد أن الصورة قد وضحت,

عدد قواسم العدد المذكور إذا كنت قد فهمت الموضوع :P

(2*2*3)^100
((2^2)*3)^100
2^200 * 3^100

d(n) = 201 + 101 = 302

عذراً على عدم استعمال latex و شكراً على توضيحك الرائع مرة أخرى :)

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

ممتاز :) إلا أنه في السطر الأخير يجب أن تحسب جداء العددين 201 و 101، وليس مجموعهما.

:)
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ,,

لا أدري لماذا أخطأت في آخر سطر رغم أني فهمت الطريقة :lol:

شكراً لتوضيحك :wink: بالمناسبة هذا هو السؤال الذي كنت أقوم بحله :

post-89451-1235643426_thumb.png

و هذا حلي الـ Super Dirty :P

#include <iostream>
#include <vector>
#include <cmath>

bool isPrime( unsigned long long number ){

if( number != 2 && number % 2 == 0 )
return false;

for( int i = 3; i < static_cast<unsigned long long>( sqrt(static_cast<double>(number)) + 1 ); i += 2 ){

if( number % i == 0 )
return false;
}

return true;
}

unsigned int p;
unsigned long long primes[1024];

void initPrimes(){

primes[0] = 2;
primes[1] = 3;
unsigned long long number = 5;

for( unsigned int i = 2; i < 1024; i++ ){

while( !isPrime(number) )
number += 2;

primes[i] = number;
number += 2;
}

return;
}


unsigned long long nextPrime(){

unsigned int ret = p;

p++;

return primes[ret];
}

unsigned long long numOfDivs( unsigned long long number ){

p = 0;
std::vector<unsigned long long> v;
unsigned long long prime = nextPrime(), divs = 1, i = 0;


while( number >= prime ){

i = 0;

while( number % prime == 0 ){
number /= prime;
i++;
}

if( i )
v.push_back( i );

prime = nextPrime();
}

for( unsigned n = 0; n < v.size(); n++ )
divs *= (v[n] + 1);

return divs;
}

unsigned long long nextTriNumber(){

static unsigned long long triNumber = 1, next = 2;

unsigned long long retTri = triNumber;

triNumber += next;
next++;

return retTri;
}

int main(){
initPrimes();

unsigned long long n = nextTriNumber();
unsigned long long divs = 500;

while( numOfDivs(n) <= divs )
n = nextTriNumber();

std::cout << n;

std::cin.get();

return 0;
}

تحياتي ,,

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

وعليكم السلام :)

هذه المسألة رقم 12 من موقع Project Euler

الجواب الصحيح هو: 76,576,500

بالبحث في غوغل، يمكنك مقارنة حلك مع محاولات الآخرين.

مثلا: 1 2 3

خالص التقدير،،

تم تعديل بواسطه caballero
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

الله ينور عليك,

على الرغم أن المغريات على النت كثيرة, إلا أنني أود أن أرى أين أعلق :lol:

أدري أني سأعلق في سؤال و لن أستطيع حله و ما بعده إلا بقدر القادر :lol:

و لكني أنتظر ذلك السؤال :)

تحياتي ,,

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكــم ورحمـة الله وبركاتــة ،،

عملت كود بالسي ولكن لم تظهر النتيجة الا بعد اكثر من ساعة !

المهم طلع نفس الناتج =76576500

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أهلاً فهد,

أعتقد أني أعرف أين المشكلة في كودك لأني وقعت في نفس الخطأ :lol:

لا تقم بإعادة حساب الأعداد الأولية مع كل رقم,

قم بإنشاء lookup table يحوي أول ألف عدد أولي على سبيل المثال و استعمل هذا الجدول لحساب القواسم.. لاحظ كودي :

هنا الأعداد الأولية و ترتيب العدد المطلوب,

unsigned int p;
unsigned long long primes[1024];

و قبل أن يبدأ البرنامج بحساب القواسم أقوم بتهيئة المصفوفة :

void initPrimes(){

primes[0] = 2;
primes[1] = 3;
unsigned long long number = 5;

for( unsigned int i = 2; i < 1024; i++ ){

while( !isPrime(number) )
number += 2;

primes[i] = number;
number += 2;
}

return;
}

بعدها قم بحساب القواسم لكل عدد دون إعادة حساب الأعداد الأولية و لكي نعود إلى بداية المصفوفة :

	p = 0;

و هكذا عندما نستدعي الدالة التالي سيتم إعادة 2, 3 و هكذا من جديد :

unsigned long long nextPrime(){

unsigned int ret = p;

p++;

return primes[ret];
}

تحياتي ,,

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

حسب السؤال اصلا لا اختبر الاعداد الاوليه

اختبر فقط الاعداد التي على الصورة

n*(n+1)/2

حتى 300 قاسم ليس هناك وقت من بعد 400 قاسم يصبح بطئ عند خمس مئه يصبح بطئ جدا

هذا الكود:

#include <stdio.h>

int main (){
int divis=300,s,t,m,i=0;

do{
i++;
t=0;
s=i*(i+1)/2;
for(m=1;m<=s;m++)
if(s%m==0) t++;
}while(t<=divis);

printf("%d",s);

getchar();
return 0;
}

لا اعلم هل يمكن ان يظهر اعداد اوليه من هذه الصورة الرياضيه غير العدد 3 ؟.

تم تعديل بواسطه فهدالشلوي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أهلاً يا فهد :)

هل ترى هذين السطرين :

for(m=1;m<=s;m++)
if(s%m==0) t++;

هما عنق الزجاجة :P

إذا لم تجد طريقة لتسريع العملية فإن برنامج سيقضي معظم وقته في هذين السطرين لكل عدد تنتجه دالتك الجميلة التي لم أكن أعرفها :)

سؤالي في بداية الموضوع كان :

ما أريد فهمه هو هل توجد طريقة لمعرفة "عدد" تلك القواسم حتى لو لم نعرف ما هي تلك القواسم,

و هذا ما أنقذنا به الزعيم caballero :lol:

تابع شرحه و ستفهم الموضوع :)

تحياتي ,,

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

طيب ياخالد سوف اعود للقراءة من البداية .

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكــم ورحمـة الله وبركاتــة ،،

for(m=1;m<=s;m++)
if(s%m==0) t++;

نعم ياخالد كانت المشكلة في السطر السابق

for(m=1;m<=sqrt(s);m++)
if(s%m==0) t++;
}while(2*t<=divis);

في ثواني ظهرت النتيجة!

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .