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

در این مطلب، روش نوشتن برنامه تجزیه عدد به عوامل اول آن مورد بررسی قرار گرفته است. فرض میشود که عدد n داده شده است. هدف، نوشتن برنامهای است که همه عوامل اول عدد n را پیدا کند. برای مثال، اگر عدد ورودی ۱۲ است، خروجی باید «۳ ۲ ۲» باشد و اگر ورودی ۳۱۵ است، خروجی باید «۷ ۵ ۳ ۳» باشد. در ادامه، گامهای لازم برای پیدا کردن کلیه عاملهای اول یک عدد ارائه شده است.
- اگر n بر ۲ تقسیمپذیر است، عدد ۲ را چاپ و سپس، n را بر ۲ تقسیم کن.
- پس از گام ۱، (اگر n بر ۲ بخشپذیر نبود) n عددی فرد است. اکنون باید حلقهای از i = 3 تا ریشه دوم n زده شود. تا هنگامی که n بر i بخشپذیر است، i را چاپ و n را بر i تقسیم کن. در هر گام، i را دو واحد افزایش و کار را ادامه بده (زیرا عدد فرد است و صرفا قرار است بر مقسومعلیههای فرد خود تقسیم شود).
- اگر n عدد اول و بزرگتر از ۲ باشد، با گامهای بالا، یک نخواهد شد. بنابراین، اگر n بزرگتر از ۲ است، آن را چاپ کن.
برنامه تجزیه عدد به عوامل اول آن در ++C
// C++ program to print all prime factors #include <bits/stdc++.h> using namespace std; // A function to print all prime // factors of a given number n void primeFactors(int n) { // Print the number of 2s that divide n while (n % 2 == 0) { cout << 2 << " "; n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (int i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { cout << i << " "; n = n/i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) cout << n << " "; } /* Driver code */ int main() { int n = 315; primeFactors(n); return 0; } // This is code is contributed by rathbhupendra
برنامه تجزیه عدد به عوامل اول آن در C
// Program to print all prime factors # include <stdio.h> # include <math.h> // A function to print all prime factors of a given number n void primeFactors(int n) { // Print the number of 2s that divide n while (n%2 == 0) { printf("%d ", 2); n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (int i = 3; i <= sqrt(n); i = i+2) { // While i divides n, print i and divide n while (n%i == 0) { printf("%d ", i); n = n/i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) printf ("%d ", n); } /* Driver program to test above function */ int main() { int n = 315; primeFactors(n); return 0; }
برنامه تجزیه عدد به عوامل اول آن در جاوا
// Program to print all prime factors import java.io.*; import java.lang.Math; class GFG { // A function to print all prime factors // of a given number n public static void primeFactors(int n) { // Print the number of 2s that divide n while (n%2==0) { System.out.print(2 + " "); n /= 2; } // n must be odd at this point. So we can // skip one element (Note i = i +2) for (int i = 3; i <= Math.sqrt(n); i+= 2) { // While i divides n, print i and divide n while (n%i == 0) { System.out.print(i + " "); n /= i; } } // This condition is to handle the case whien // n is a prime number greater than 2 if (n > 2) System.out.print(n); } public static void main (String[] args) { int n = 315; primeFactors(n); } }
برنامه تجزیه عدد به عوامل اول آن در پایتون
# Python program to print prime factors import math # A function to print all prime factors of # a given number n def primeFactors(n): # Print the number of two's that divide n while n % 2 == 0: print 2, n = n / 2 # n must be odd at this point # so a skip of 2 ( i = i + 2) can be used for i in range(3,int(math.sqrt(n))+1,2): # while i divides n , print i ad divide n while n % i== 0: print i, n = n / i # Condition if n is a prime # number greater than 2 if n > 2: print n # Driver Program to test above function n = 315 primeFactors(n) # This code is contributed by Harshit Agrawal
برنامه تجزیه عدد به عوامل اول آن در #C
// C# Program to print all prime factors using System; namespace prime { public class GFG { // A function to print all prime // factors of a given number n public static void primeFactors(int n) { // Print the number of 2s that divide n while (n % 2 == 0) { Console.Write(2 + " "); n /= 2; } // n must be odd at this point. So we can // skip one element (Note i = i +2) for (int i = 3; i <= Math.Sqrt(n); i+= 2) { // While i divides n, print i and divide n while (n % i == 0) { Console.Write(i + " "); n /= i; } } // This condition is to handle the case whien // n is a prime number greater than 2 if (n > 2) Console.Write(n); } // Driver Code public static void Main() { int n = 315; primeFactors(n); } } } // This code is contributed by Sam007
برنامه تجزیه عدد به عوامل اول آن در PHP
<?php // PHP Efficient program to print all // prime factors of a given number // function to print all prime // factors of a given number n function primeFactors($n) { // Print the number of // 2s that divide n while($n % 2 == 0) { echo 2," "; $n = $n / 2; } // n must be odd at this // point. So we can skip // one element (Note i = i +2) for ($i = 3; $i <= sqrt($n); $i = $i + 2) { // While i divides n, // print i and divide n while ($n % $i == 0) { echo $i," "; $n = $n / $i; } } // This condition is to // handle the case when n // is a prime number greater // than 2 if ($n > 2) echo $n," "; } // Driver Code $n = 315; primeFactors($n); // This code is contributed by aj_36 ?>
خروجی حاصل از برنامه تجزیه عدد به عوامل اول
در ادامه، خروجیهای قطعه کد بالا برای 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
سلام لطفا برنامه تجزیه اعداد اول یک عدد را درمتلب بنویسید