برنامه نویسی، ریاضی ۱۰۹۵۳ بازدید

در این مطلب، روش نوشتن برنامه تجزیه عدد به عوامل اول آن مورد بررسی قرار گرفته است. فرض می‌شود که عدد 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; 
}

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

// 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 برابر با ۱ یا یک عدد اول شود.

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

^^

بر اساس رای ۱۷ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

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

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر