Berilgan sonning barcha tub bo'luvchilarini topishning samarali usullaridan biri

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


 Javohir Developer - Texnoman foydalanuvchisi

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!