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

در این مطلب، روش نوشتن برنامه تجزیه عدد به عوامل اول آن مورد بررسی قرار گرفته است. فرض می‌شود که عدد n داده شده است. هدف، نوشتن برنامه‌ای است که همه عوامل اول عدد n را پیدا کند. برای مثال، اگر عدد ورودی ۱۲ است، خروجی باید «۳ ۲ ۲» باشد و اگر ورودی ۳۱۵ است، خروجی باید «۷ ۵ ۳ ۳» باشد. در ادامه، گام‌های لازم برای پیدا کردن کلیه عامل‌های اول یک عدد ارائه شده است.

1. اگر n بر ۲ تقسیم‌پذیر است، عدد ۲ را چاپ و سپس، n را بر ۲ تقسیم کن.
2. پس از گام ۱، (اگر n بر ۲ بخش‌پذیر نبود) n عددی فرد است. اکنون باید حلقه‌ای از  i = 3 تا ریشه دوم n زده شود. تا هنگامی که n بر i بخش‌پذیر است، i را چاپ و n را بر i تقسیم کن. در هر گام، i را دو واحد افزایش و کار را ادامه بده (زیرا عدد فرد است و صرفا قرار است بر مقسوم‌علیه‌های فرد خود تقسیم شود).
3. اگر n عدد اول و بزرگ‌تر از ۲ باشد، با گام‌های بالا، یک نخواهد شد. بنابراین، اگر n بزرگ‌تر از ۲ است، آن را چاپ کن.

برنامه تجزیه عدد به عوامل اول آن در ++C

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

فیلم آموزش مبانی برنامه نویسی – الگوریتم و فلوچارت با رویکرد حل مساله در فرادرس

کلیک کنید

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

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

فیلم آموزش برنامه نویسی پایتون Python – مقدماتی + گواهینامه در فرادرس

کلیک کنید

برنامه تجزیه عدد به عوامل اول آن در #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) — به زبان ساده

^^