Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714631

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

Eretasfen Galviri O(n log log n)

 

Bu algoritm maqsadi asosan 1n gacha bolgan tub sonlarni topishdir. Bu algoritm juda kop foydalaniladi shu sababli bu algoritmni organishingiz zarur.

 

Goyasi : bu algoritmda 1n gacha bolgan sonlardan barcha 2 bolinadigan 2 dan tashqari, barcha 3 bolinadigan 3 dan tashqari, barcha 5 bolinadigan 5 dan tashqari, barcha 7 bolinadigan 7 dan tashqari, barcha 11 bolinadigan 11 dan tashqari, barcha 13 bolinadigan 13 dan tashqari . Sonlar true qilinadi true bolmagan sonlar tub sonlardir masalan 124 uchun

2-- (4,6,8,10,12,14,16,18,20,22,24)

3-- (6,9,12,15,18,21,24)

5-- (10,15,20)

7-- (14,21)

11--(22)

13-- (yoq)

17-- (yoq)

19-- (yoq)

23-- (yoq)

Endi true qilgan sonlarimizni yozib koramiz.

1,4,6,8,9,10,12,14,15,16,18,20,21,22,24 qarabsizki bu yerda yoq sonlar tub boladi.

Endi siz bilan shu algoritm realizatsiyasini korib chiqamiz albatta buni xar dasturchi xar qilib yozishi mumkin. Men buni ozim tushunishim boyicha yozganman siz xam buni ozingiz tushunishingiz boyicha yozishingiz mumkin.

JAVA tilidagi kod

 

import java.util.Scanner;

 

public class ERETASFEN {

public static void main(String[] args) {

Scanner sc= new Scanner(System.in);

int m=sc.nextInt();

boolean used[]=new boolean[m+2];

used[1]=true;

for (int i =2; i <=m; i++) {

if(!used[i]){

int k=2;

while(k*i<=m){

used[k*i]=true;

k++;

}

}

}

for (int i =1; i <=m; i++) {

if(!used[i])

System.out.print(i+" ");

}

}

Endi esa siz bilan shu kodni pascal tilida yozamiz:

 

var

i,n,k:integer;

used:array[1..1000000]of boolean;

begin

read(n);

used[1]:=true;

for i:=2 to n do

if(used[i]=false) then

begin

k:=2;

while(k*i<=n) do

begin

used[k*i]:=true;

k:=k+1;

end;

end;

for i:=1 to n do

if(used[i]=false) then

write(i, ' ');

end.

 

C++ tiladagi boshqacha kodi:

 

int n;

vector<char> prime (n+1, true);

prime[0] = prime[1] = false;

for (int i=2; i<=n; ++i)

if (prime[i])

for (int j=i*i; j<=n; j+=i)

prime[j] = false;

 

Tub sonlarga doir bolgan bazi misollar quyidagilar:

 

acmp.ru 0060, 0064, 0292, 0335,0349,0354,0516

acm.tuit.uz 0141,0166,0171,K001,K002,M006

algo.urgench-tuit.uz 245,246,247,248,249,253,254,273

va boshqa saytlar orqali misollarni yechib koring.

 

 

 

 

Ro`yxatga qaytish        Muallifi: Bahrom Sultonov