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

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

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

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

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

1// C++ program to print all prime factors  
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5// A function to print all prime  
6// factors of a given number n  
7void primeFactors(int n)  
8{  
9    // Print the number of 2s that divide n  
10    while (n % 2 == 0)  
11    {  
12        cout << 2 << " ";  
13        n = n/2;  
14    }  
15  
16    // n must be odd at this point. So we can skip  
17    // one element (Note i = i +2)  
18    for (int i = 3; i <= sqrt(n); i = i + 2)  
19    {  
20        // While i divides n, print i and divide n  
21        while (n % i == 0)  
22        {  
23            cout << i << " ";  
24            n = n/i;  
25        }  
26    }  
27  
28    // This condition is to handle the case when n  
29    // is a prime number greater than 2  
30    if (n > 2)  
31        cout << n << " ";  
32}  
33  
34/* Driver code */
35int main()  
36{  
37    int n = 315;  
38    primeFactors(n);  
39    return 0;  
40}  
41  
42// This is code is contributed by rathbhupendra

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

1// Program to print all prime factors 
2# include <stdio.h> 
3# include <math.h> 
4  
5// A function to print all prime factors of a given number n 
6void primeFactors(int n) 
7{ 
8    // Print the number of 2s that divide n 
9    while (n%2 == 0) 
10    { 
11        printf("%d ", 2); 
12        n = n/2; 
13    } 
14  
15    // n must be odd at this point.  So we can skip  
16    // one element (Note i = i +2) 
17    for (int i = 3; i <= sqrt(n); i = i+2) 
18    { 
19        // While i divides n, print i and divide n 
20        while (n%i == 0) 
21        { 
22            printf("%d ", i); 
23            n = n/i; 
24        } 
25    } 
26  
27    // This condition is to handle the case when n  
28    // is a prime number greater than 2 
29    if (n > 2) 
30        printf ("%d ", n); 
31} 
32  
33/* Driver program to test above function */
34int main() 
35{ 
36    int n = 315; 
37    primeFactors(n); 
38    return 0; 
39}

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

1// Program to print all prime factors 
2import java.io.*; 
3import java.lang.Math; 
4  
5class GFG 
6{ 
7    // A function to print all prime factors 
8    // of a given number n 
9    public static void primeFactors(int n) 
10    { 
11        // Print the number of 2s that divide n 
12        while (n%2==0) 
13        { 
14            System.out.print(2 + " "); 
15            n /= 2; 
16        } 
17  
18        // n must be odd at this point.  So we can 
19        // skip one element (Note i = i +2) 
20        for (int i = 3; i <= Math.sqrt(n); i+= 2) 
21        { 
22            // While i divides n, print i and divide n 
23            while (n%i == 0) 
24            { 
25                System.out.print(i + " "); 
26                n /= i; 
27            } 
28        } 
29  
30        // This condition is to handle the case whien 
31        // n is a prime number greater than 2 
32        if (n > 2) 
33            System.out.print(n); 
34    } 
35  
36    public static void main (String[] args) 
37    { 
38        int n = 315; 
39        primeFactors(n); 
40    } 
41}

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

1# Python program to print prime factors 
2  
3import math 
4  
5# A function to print all prime factors of  
6# a given number n 
7def primeFactors(n): 
8      
9    # Print the number of two's that divide n 
10    while n % 2 == 0: 
11        print 2, 
12        n = n / 2
13          
14    # n must be odd at this point 
15    # so a skip of 2 ( i = i + 2) can be used 
16    for i in range(3,int(math.sqrt(n))+1,2): 
17          
18        # while i divides n , print i ad divide n 
19        while n % i== 0: 
20            print i, 
21            n = n / i 
22              
23    # Condition if n is a prime 
24    # number greater than 2 
25    if n > 2: 
26        print n 
27          
28# Driver Program to test above function 
29  
30n = 315
31primeFactors(n) 
32  
33# This code is contributed by Harshit Agrawal

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

1// C# Program to print all prime factors 
2using System; 
3  
4namespace prime 
5{ 
6public class GFG 
7{      
8                  
9    // A function to print all prime  
10    // factors of a given number n 
11    public static void primeFactors(int n) 
12    { 
13        // Print the number of 2s that divide n 
14        while (n % 2 == 0) 
15        { 
16            Console.Write(2 + " "); 
17            n /= 2; 
18        } 
19  
20        // n must be odd at this point. So we can 
21        // skip one element (Note i = i +2) 
22        for (int i = 3; i <= Math.Sqrt(n); i+= 2) 
23        { 
24            // While i divides n, print i and divide n 
25            while (n % i == 0) 
26            { 
27                Console.Write(i + " "); 
28                n /= i; 
29            } 
30        } 
31  
32        // This condition is to handle the case whien 
33        // n is a prime number greater than 2 
34        if (n > 2) 
35            Console.Write(n); 
36    } 
37      
38    // Driver Code 
39    public static void Main() 
40    { 
41        int n = 315; 
42        primeFactors(n); 
43    } 
44  
45}  
46} 
47  
48// This code is contributed by Sam007

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

1<?php 
2// PHP Efficient program to print all 
3// prime factors of a given number 
4  
5// function to print all prime  
6// factors of a given number n 
7function primeFactors($n) 
8{ 
9      
10    // Print the number of 
11    // 2s that divide n 
12    while($n % 2 == 0) 
13    { 
14        echo 2," "; 
15        $n = $n / 2; 
16    } 
17  
18    // n must be odd at this  
19    // point. So we can skip  
20    // one element (Note i = i +2) 
21    for ($i = 3; $i <= sqrt($n);  
22                   $i = $i + 2) 
23    { 
24          
25        // While i divides n,  
26        // print i and divide n 
27        while ($n % $i == 0) 
28        { 
29            echo $i," "; 
30            $n = $n / $i; 
31        } 
32    } 
33  
34    // This condition is to  
35    // handle the case when n  
36    // is a prime number greater 
37    // than 2 
38    if ($n > 2) 
39        echo $n," "; 
40} 
41  
42    // Driver Code 
43    $n = 315; 
44    primeFactors($n); 
45  
46// This code is contributed by aj_36 
47?>

خروجی حاصل از برنامه تجزیه عدد به عوامل اول

در ادامه، خروجی‌های قطعه کد بالا برای 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
۴ دیدگاه برای «برنامه تجزیه عدد به عوامل اول آن — به زبان ساده»

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

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

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

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

نظر شما چیست؟

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