Printable View
اعداد متحابه رو که می دونید چین؟
دو عدد را” متحابه” گوییم هرگاه مجموع مقسوم علیه های هر یک با دیگری برابر باشد. به عنوان مثال اعداد ۲۸۴ و ۲۲۰ را در نظر بگیرید مجموع مقسوم علیه های عدد ۲۸۴ برابر با عدد ۲۲۰ است و مجموع مقسوم علیه های عدد ۲۲۰ برابر با ۲۸۴ است.
خوب؟
الگوریتمی می خوام که اعداد متحابه کمتر از 1000000 رو پیدا کنه. سرعتش واقعا مهمه.
ممنون
سلام
نمی‌دونم این چیزی که می‌گم کاملا درسته یا نه...
اما بهتره قبل از هر چیزی اعداد اول کمتر از 1000000 را به دست بیاوری...
بعد با استفاده از اعداد اول (تمام حالت‌های جمع) رو به دست بیار و در عین حال اعدادی که از این اعداد اول به دست می‌ایند رو نیز برای متحابه بودن، با هم مقایسه کن...
خلاصه اینکه بهتره از اعداد اول به عنوان پایه‌ای برای تصمیم گیری و ساخت اعداد متحابه استفاده کنی...
مطمئنا تعداد اعداد اول کمتر از 1000000 اینقدر کم هست که بشه تمام حالت‌ها رو به سرعت تولید کرد.
موفق باشی
نه نمیشه ؛
حتی همین قسمت کار هم کلی وقت می گیره ؛ حالا شما تصور کنید ما اعداد اول رو + اعدادی که مجموع مقسوم علیه هاشون از 1000000 بیشتره رو هم حذف کنیم ( با وجود اینکه pc هنگ می کنه با این راههای عادی!!!) ؛ بازم دوتا آرایه ی n عضوی داریم که باید همه ی اونا رو یک به یک از نظر تساوی با هم مقایسه کنیم... می دونید چه وقتی می خواد؟؟
باید راه سریعتری باشه..
شما به یک قضیه احتیاج دارید که مسئله را ساده تر کند.
مثل قضیه ای که برای اعداد اول است "هر عدد nغیر او ،مقسوم علیه کوچکتری از رادیکال n دارد"
برای یک میلیون عدد چه مدت زمان برای شما قابل قبول هست؟نقل قول:
نوشته شده توسط mary_23