Berilgan sonning barcha tub bo’luvchilarini topishning samarali usullaridan biri

Avvalambor Assalomu alaykum. Bu darsimda sizlarni sonning barcha tub bo’luvchilarini topish algoritmi bilan tanishtirmoqchiman.Tub son deb faqat o’ziga va 1 ga bo’linadigan songa aytiladi.Demak boshladik:

1. Berilgan sonni n deb belgilab olamiz.
2. Agarda n soni 2 ga bo’linsa, ekranga 2 ni chiqaramiz va n ni 2 ga bo’lamiz(Bu amal n soni 2 ga bo’linmay qolguncha bajariladi)
3. Keyingi bo’luvchilar albatta toq sonlar bo’ladi. Shuning uchun i=3 dan n ning kvadrat ildizigacha sikl yurgazamiz va n soni i ga bo’linmay qolguncha ularni bo’lib ekranga i ni chiqaraveramiz. Aytgancha i ni oshirishda i=i+2 qilsangiz bo’ladi.Chunki keyingi bo’luvchilar albatta toq sonlar bo’ladi degan edik
4. Oxirgi qadamda n>2 bo’lsa n ni ham ekranga chiqaramiz.Chunki bu paytda n ham tub son bo’lib qolgan bo’ladi.

Keling misollar bilan tushuntirishga harakat qilaman. Misol uchun n=400 bo’lgan holda n ning tub bo’luvchilarini topamiz:

Keling endi tepadagi algoritmdagi 4-qadamga e’tiborizni qarataman. Bu yerda «nega n>2 bo’lganda n tub son bo’ladi ?» deb o’ylagan bo’lishiz mumkin. Buni n=52 bo’lganda ko’rib chiqamiz:

Ko’rib turganingizdek bu yerda 13>2 va oxirida tub bo’lib qoldi. Biz yurgazadigan sikl faqat sqrt(n) gacha boradi. sqrt(52)

O’ylashim bo’yicha buni tushundingiz. Keling endi ushbu algoritmning dasturini tuzamiz:(Tavsiya : Algoritmni tushungan bo’lsangiz kodni ko’rmasdan o’zingiz yozishga harakat qilib ko’rishingiz mumkin)

C++

#include  
#include 
using namespace std;
//Barcha tub bo'luvchilarni chiqaruvchi funksiya hosil qilamiz
void primeFactors(int n) 
{ 
 // Oldin n ni 2 (tub son)ga bo'lib chiqamiz.Bu hol n soni 2 ga bo'linmay qolguncha davom etadi 
 while (n%2 == 0) 
 { 
        printf("%d ", 2); 
        n = n/2; 
 } 
 // bundan keyingi bo'luvchilar albatta toq sonlar bo'ladi 
 // i lar toq son bo'lgani uchun uni i=i+2 qilshimiz mumkin 
 for (int i = 3; i 2 bo'lsa n tub son bo'ladi. Shuni uchun uni o'zini chop qilamiz
 if (n > 2) 
        printf ("%d ", n); 
} 
//Dasturning asosiy qismi
int main() 
{ 
 cout>n; 
 primeFactors(n); 
 return 0; 
}

Java

Java kodda izohlar berib o’tirmadim. Java va c++ tillari bir biriga deyarli o’xshash bo’lgani uchun c++ kodidagi izohlardan foydalanishingiz mumkin

import java.util.Scanner;
import java.lang.Math; 
class factorization
{ 
    public static void primeFactors(int n) 
    { 
        while (n%2==0) 
        { 
            System.out.print(2 + " "); 
            n /= 2; 
        } 
             for (int i = 3; i  2) 
            System.out.print(n); 
    } 
    public static void main (String[] args) 
    { 
        Scanner sc = new Scanner(System.in);
        System.out.print("N ni kiriting : "); 
        int n = sc.nextInt(); 
        primeFactors(n); 
    } 
}

Shunday qilib algoritmni yaxshi tushuntira oldim deb umid qilaman. Agarda maqola bo’yicha taklif yoki mulohazalar bo’lsa telegramda @Junior_Coder ga yoki maqolaning izohlar qismiga yozishingiz mumkin. E’tiboringiz uchun raxmat!

Foydalanilgan manbalar : geeksforgeeks,wikipedia