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:
- Berilgan sonni n deb belgilab olamiz.
- 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)
- 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
- 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
Fikrlar 1