1

Mavzu: Erotosfen g'alviri

                             Erotosfen ga'lviri             


A dan B gacha bo'lgan tub sonlarni topish kerak bo'lsin. Bu uchun A dan B gacha har bir sonni olib tekshirib chiqish mumkin. Lekin, buning boshqacharoq usuli ham bor. Ya'ni tezroq ishlaydigan. Faqat bu uchun sal xotira talab qilinadi (N o'lchamli qo'shimcha boolean massiv).

Bu masalani Erotosfen g'alviri yordamida ishlaymiz. Bu usulda quyidagicha yo'l tutiladi:

2 dan N gacha bo'lgan sonlarni yozib chiqamiz. Bir boshdan qarab, hali o'chirilmagan sonni olamiz va barcha shu songa bo'linadigan sonlarni o'chirib chiqamiz. Masalan, o'sha sonimiz a  bo'ladigan bo'lsa, 2 * a, 3 * a, 4 * a ...  larni qatorimizdan o'chirib tashlaymiz. Chunki ular murakkab son. So'ng, keyingi o'chirilmagan sonni olib shu ishni qilamiz va hk.

Natijada barcha tub sonlar o'chmay qoladi. Qolganlarini o'chirgan bo'lamiz.

Masalan:
f - o'chmagan,  t - o'chgan

1)


f    f    f    f    f    f    f    f     f      f      f      f      f      f      f      f      f      f      f     

2   3   4   5   6   7   8   9   10    11   12    13   14    15   16   17    18   19    20


2)

1-o'chmagan son 2 ni olib unga bo'linadigan sonlarni o'chiramiz (2 dan tashqari):


f    f    t    f    t    f    t    f    t      f      t      f      t      f      t      f      t      f      t     

2   3   4   5   6    7   8   9   10    11   12   13   14    15   16   17    18   19    20


3)

2-o'chmagan son 3 ni olib unga bo'linadigan sonlarni ham o'chiramiz (3 dan tashqari):


f    f    t    f    t    f    t    t    t      f      t      f      t      t      t      f      t      f      t     

2   3   4   5   6    7   8   9   10    11   12   13   14    15   16   17    18   19    20


4)

3-o'chmagan son 5 ni olib unga bo'linadigan sonlarni ham o'chiramiz (5 dan tashqari):


f    f    t    f    t    f    t    t    t      f      t      f      t      t      t      f      t      f      t     

2   3   4   5   6    7   8   9   10    11   12   13   14    15   16   17    18   19    20


va hk.

Shu ishni 2 dan N gacha bo'lgan barcha sonlar uchun qilib chiqsak, ketma-ketligimizda faqat tub sonlar o'chmay qoladi.

Bu usul katta oraliqdagi tub sonlarni tez topishda ishlatiladi. Masalan 1 dan 10^7 gacha.

Kodi Delphida:

Var a:boolean[2..10000000] of Boolean;
       i, j, N : Integer;
Begin
readln(N);

for i:=2 to N do
  if not a[i] then begin

     j:=2;
      
      while (i * j <= N) do begin
        a[i * j] := true;
        inc(j);
      end;

  end;
 
writeln('1 dan ',N,' gacha bo''lgan tub sonlar:');

for i:=2 to N do 
   if not a[i] then write(i,' ');

End.

Erotosfen g'alviri ga javob

har gal i*j ma'lum bir operatsiyalarni sonini oshiradi uning o'rniga qo'shish amali tezroq ishlaydi va bu kodni quyidagi ko'rinishda yozsak ham bo'ladi:

#include<stdio.h>
bool a[10000001]={0};
int main()
{
    a[0]=true;
    a[1]=true;
    int n;
    scanf("%i",&n);
    for(int i=2;i<=n;i++)
       if(!a[i])
       {
          for(int j=i*2;j<=n;j+=i)
              a[j]=true;
          printf("%i ",i);
       }
    return 0;
}

Erotosfen g'alviri ga javob

Nodirbek, qarang:

 while (i * j <= N) do begin
        a[i * j] := true;
        inc(j);
      end;

bundagi inc(j) nima qiladi

Erotosfen g'alviri ga javob

nima vazifa bajaradi demoqchiman

Erotosfen g'alviri ga javob

inc(j)   bu j ni qiymatini 1 ga oshirish, ya'ni j++;

Erotosfen g'alviri ga javob

  while (i * j <= N) do begin
        a[i * j] := true;
        j := j + 1;
  end;

Erotosfen g'alviri ga javob

Quyidagi masalalarni shu usul bilan ishlab ko'ring:

0166. TUB SONLAR
0141. Kvadratsiz son
0163. DO’ST SONLAR
K003. Bo’luvchilar soni

Erotosfen g'alviri ga javob

It's due to this fact doable that these components have been written for one of these public performances.

Visit site: Music for romantic

https://audiojungle.net/user/momentumof … umOfMelody
https://audiojungle.net/item/piano-insp … umOfMelody
https://audiojungle.net/user/ie_sound/p … f=IE_Sound
https://audiojungle.net/item/motivation … f=IE_Sound