برنامه تجزیه عدد به عوامل اول آن – به زبان ساده


در این مطلب، روش نوشتن برنامه تجزیه عدد به عوامل اول آن مورد بررسی قرار گرفته است. فرض میشود که عدد n داده شده است. هدف، نوشتن برنامهای است که همه عوامل اول عدد n را پیدا کند. برای مثال، اگر عدد ورودی ۱۲ است، خروجی باید «۳ ۲ ۲» باشد و اگر ورودی ۳۱۵ است، خروجی باید «۷ ۵ ۳ ۳» باشد. در ادامه، گامهای لازم برای پیدا کردن کلیه عاملهای اول یک عدد ارائه شده است.
- اگر n بر ۲ تقسیمپذیر است، عدد ۲ را چاپ و سپس، n را بر ۲ تقسیم کن.
- پس از گام ۱، (اگر n بر ۲ بخشپذیر نبود) n عددی فرد است. اکنون باید حلقهای از i = 3 تا ریشه دوم n زده شود. تا هنگامی که n بر i بخشپذیر است، i را چاپ و n را بر i تقسیم کن. در هر گام، i را دو واحد افزایش و کار را ادامه بده (زیرا عدد فرد است و صرفا قرار است بر مقسومعلیههای فرد خود تقسیم شود).
- اگر n عدد اول و بزرگتر از ۲ باشد، با گامهای بالا، یک نخواهد شد. بنابراین، اگر n بزرگتر از ۲ است، آن را چاپ کن.
برنامه تجزیه عدد به عوامل اول آن در ++C
برنامه تجزیه عدد به عوامل اول آن در C
برنامه تجزیه عدد به عوامل اول آن در جاوا
برنامه تجزیه عدد به عوامل اول آن در پایتون
برنامه تجزیه عدد به عوامل اول آن در #C
برنامه تجزیه عدد به عوامل اول آن در PHP
خروجی حاصل از برنامه تجزیه عدد به عوامل اول
در ادامه، خروجیهای قطعه کد بالا برای n = ۳۱۵ محاسبه شده است.
3 3 5 7
روش کار قطعه کدهای بالا
در گامهای ۱ و ۲ به اعداد مرکب و در گام ۳ به اعداد اول پرداخته میشود. برای اثبات اینکه الگوریتم کامل کار میکند، نیاز به اثبات این است که گامهای ۱ و ۲ به اعداد مرکب میپردازند. واضح است که در گام ۱، اعداد زوج مورد بررسی قرار میگیرند.
پس از گام اول، همه فاکتورهای اول باقیمانده باید فرد باشند (تفاوت دو عامل اول حداقل باید دو باشد)، به همین دلیل است که i در هر گام، دو واحد افزایش پیدا میکند. اکنون، بخش اصلی مربوط به حلقهای است که تا ریشه دوم n ادامه پیدا میکند. برای اثبات اینکه این روش به درستی عمل میکند، خصوصیت زیر از اعداد مرکب در نظر گرفته میشود.
هر عدد مرکب، حداقل یک عامل اول کوچکتر یا مساوی ریشه دوم خود دارد.
این خصوصیت را میتوان با استفاده از عبارت نقیض اثبات کرد. فرض میشود a و b دو عامل n هستند، به طوریکه a*b = n. اگر هر دو این موارد بزرگتر از n√ باشند، a.b > √n و n√* که با عبارت a * b = n تناقض دارد. در گام ۲ از الگوریتم، حلقه اجرا و اقدامات زیر در آن انجام میشود:
- کوچکترین فاکتور اول i را پیدا کن (باید کمتر از n√ باشد)
- همه وقوعهای i در n را با تقسیم مکرر n بر i، پیدا کن
- گامهای a و b را برای n و i = i + 2 پیدا کن. گامهای a و b تا هنگامی تکرار میشوند که n برابر با ۱ یا یک عدد اول شود.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پسگرد (Backtracking) — به زبان ساده
^^
میشه توضیح بدید چطور این الگوریتم فقط اعداد اول را برمیگردانه و مثلا عدد 15 در خروجی نشان نمیده
سلام ببینید اعدادی که اول نیستند از تعدادی عوامل اول ساخته شده اند که عوامل عدد غیر اول x از x کوچکتر است
و اگر دقت کنید در جایی که بخش پذیری تایید میشد عدد ورودی تقسیم بر آن عدد میشد و برای مثال اگر عدد 12 را به آن میدادیم
عدد 12 در ابتدا 2 بار 2 چاپ میکند و عدد تبدیل به 3 میشود و سپس به 1 و وقتی که حلقه به 6 برسد دیگر 1 بر 6 بخش پذیر نیست و اینطور دیگر نیازی به نوشتن تابع عدد اول و کند شدن برنامه نیست
سورس کد تجزیه اعداد بر پای ۱۰ رو میخوام مثال :
125 = 1*10^2+2*10^1+5*10^0
سلام لطفا برنامه تجزیه اعداد اول یک عدد را درمتلب بنویسید