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

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

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

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

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎

اینجا کلیک کنید

// 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 – مقدماتی

اینجا کلیک کنید

# 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) — به زبان ساده

^^