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

۶۶۴۶ بازدید
آخرین به‌روزرسانی: ۱۹ اردیبهشت ۱۴۰۲
زمان مطالعه: ۶ دقیقه
دانلود PDF مقاله
برنامه تجزیه عدد به عوامل اول آن – به زبان سادهبرنامه تجزیه عدد به عوامل اول آن – به زبان ساده

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

997696
  1. اگر n بر ۲ تقسیم‌پذیر است، عدد ۲ را چاپ و سپس، n را بر ۲ تقسیم کن.
  2. پس از گام ۱، (اگر n بر ۲ بخش‌پذیر نبود) n عددی فرد است. اکنون باید حلقه‌ای از  i = 3 تا ریشه دوم n زده شود. تا هنگامی که n بر i بخش‌پذیر است، i را چاپ و n را بر i تقسیم کن. در هر گام، i را دو واحد افزایش و کار را ادامه بده (زیرا عدد فرد است و صرفا قرار است بر مقسوم‌علیه‌های فرد خود تقسیم شود).
  3. اگر 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 برابر با ۱ یا یک عدد اول شود.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۲۲ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
دانلود PDF مقاله
۴ دیدگاه برای «برنامه تجزیه عدد به عوامل اول آن – به زبان ساده»

میشه توضیح بدید چطور این الگوریتم فقط اعداد اول را برمیگردانه و مثلا عدد 15 در خروجی نشان نمیده

سلام ببینید اعدادی که اول نیستند از تعدادی عوامل اول ساخته شده اند که عوامل عدد غیر اول x از x کوچکتر است
و اگر دقت کنید در جایی که بخش پذیری تایید میشد عدد ورودی تقسیم بر آن عدد میشد و برای مثال اگر عدد 12 را به آن میدادیم
عدد 12 در ابتدا 2 بار 2 چاپ میکند و عدد تبدیل به 3 میشود و سپس به 1 و وقتی که حلقه به 6 برسد دیگر 1 بر 6 بخش پذیر نیست و اینطور دیگر نیازی به نوشتن تابع عدد اول و کند شدن برنامه نیست

سورس کد تجزیه اعداد بر پای ۱۰ رو میخوام مثال :
125 = 1*10^2+2*10^1+5*10^0

سلام لطفا برنامه تجزیه اعداد اول یک عدد را درمتلب بنویسید

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *