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)<13 . Demak 13 gacha tekshira olmaymiz va shuning uchun 13 ni o'zini chiqarib qo'yamiz.

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 <iostream> 
#include <math.h>
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 <= sqrt(n); i = i+2) 
 { 
        // i soni n ga bo'lingan paytda , i ni chop qilsin va n ni i ga bo'lsin.Bu amallar ham i soni n ga bo'linmay qolguncha davom etadi
        while (n%i == 0) 
        { 
            printf("%d ", i); 
            n = n/i; 
        } 
 } 
 //bu tepadagi algoritmdagi 4-qismdir
 // ya'ni n>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 ni kiriting : ";
 int n;
 cin>>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 <= Math.sqrt(n); i+= 2) 
        { 
            while (n%i == 0) 
            { 
                System.out.print(i + " "); 
                n /= i; 
            } 
        } 
       if (n > 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


Javohir707

Muallif haqida

Javohir Developer Java, JavaFX, Android, PHP, C++, Js Junior Competitive Programmer :D


Blogdagi so‘nggi maqolalar:


Fikrlar 1

muhammadsalah
muhammadsalah
nima bu
Iltimos, fikr bildirish uchun saytga kiring yoki ro‘yxatdan o‘ting!