PDA

View Full Version : سوال: کشف اعداد متحابه ولی پرسرعت!!!



mary_23
دوشنبه 24 تیر 1387, 16:35 عصر
اعداد متحابه رو که می دونید چین؟

دو عدد را” متحابه” گوییم هرگاه مجموع مقسوم علیه های هر یک با دیگری برابر باشد. به عنوان مثال اعداد ۲۸۴ و ۲۲۰ را در نظر بگیرید مجموع مقسوم علیه های عدد ۲۸۴ برابر با عدد ۲۲۰ است و مجموع مقسوم علیه های عدد ۲۲۰ برابر با ۲۸۴ است.

خوب؟
الگوریتمی می خوام که اعداد متحابه کمتر از 1000000 رو پیدا کنه. سرعتش واقعا مهمه.

ممنون

amir_saniyan
سه شنبه 25 تیر 1387, 18:20 عصر
سلام

نمی‌دونم این چیزی که می‌گم کاملا درسته یا نه...

اما بهتره قبل از هر چیزی اعداد اول کمتر از 1000000 را به دست بیاوری...
بعد با استفاده از اعداد اول (تمام حالت‌های جمع) رو به دست بیار و در عین حال اعدادی که از این اعداد اول به دست می‌ایند رو نیز برای متحابه بودن، با هم مقایسه کن...

خلاصه اینکه بهتره از اعداد اول به عنوان پایه‌ای برای تصمیم گیری و ساخت اعداد متحابه استفاده کنی...

مطمئنا تعداد اعداد اول کمتر از 1000000 اینقدر کم هست که بشه تمام حالت‌ها رو به سرعت تولید کرد.

موفق باشی

mary_23
چهارشنبه 26 تیر 1387, 14:24 عصر
نه نمیشه ؛
حتی همین قسمت کار هم کلی وقت می گیره ؛ حالا شما تصور کنید ما اعداد اول رو + اعدادی که مجموع مقسوم علیه هاشون از 1000000 بیشتره رو هم حذف کنیم ( با وجود اینکه pc هنگ می کنه با این راههای عادی!!!) ؛ بازم دوتا آرایه ی n عضوی داریم که باید همه ی اونا رو یک به یک از نظر تساوی با هم مقایسه کنیم... می دونید چه وقتی می خواد؟؟

باید راه سریعتری باشه..

رضا عربلو
چهارشنبه 26 تیر 1387, 16:03 عصر
شما به یک قضیه احتیاج دارید که مسئله را ساده تر کند.
مثل قضیه ای که برای اعداد اول است "هر عدد nغیر او ،مقسوم علیه کوچکتری از رادیکال n دارد"

linux
چهارشنبه 26 تیر 1387, 19:29 عصر
اعداد متحابه رو که می دونید چین؟

دو عدد را” متحابه” گوییم هرگاه مجموع مقسوم علیه های هر یک با دیگری برابر باشد. به عنوان مثال اعداد ۲۸۴ و ۲۲۰ را در نظر بگیرید مجموع مقسوم علیه های عدد ۲۸۴ برابر با عدد ۲۲۰ است و مجموع مقسوم علیه های عدد ۲۲۰ برابر با ۲۸۴ است.

خوب؟
الگوریتمی می خوام که اعداد متحابه کمتر از 1000000 رو پیدا کنه. سرعتش واقعا مهمه.

ممنون
برای یک میلیون عدد چه مدت زمان برای شما قابل قبول هست؟

linux
پنج شنبه 27 تیر 1387, 10:26 صبح
http://en.wikipedia.org/wiki/Amicable_number