Eratosfen

Dasturlash bo’yicha algoritmlarni o’rganib boshlaganlar birinchilardan bo’lib tub sonlarni topish bo’yicha Eratosfen g’alvirini o’rganishadi. Eratosfen g’alviri tub sonlarni topuvchi effektiv algoritmlardan biri bo’lib, uning psevdokodi quyidagicha:

i := 2, 3, 4, ..., while i ≤ n:

  if A[i] = true:

    j := 2i, 3i, 4i, ..., while j ≤ n:

         A[j] := false

Yangi dastruchilar bu algoritmning effektiv ekanligiga unchalik ishonishmaydi chunki unda ichma-ich ikki sikl mavjud. Bu algoritmdagi bajariladigan amallar sonini taxminan quyidagi yi’gindi bilan ifodalashimiz mumkin:

 – x sonining butun qismi.

Sizning vazifangiz Eratosfen algoritmining effektiv ekanligini isbotlash, buning uchun berilgan summaning qiymatini topadigan dastur tuzishngiz kerak.

Kiruvchi ma’lumotlar

Birinchi qatorda n natural soni beriladi(1≤n≤2∙10⁹).

Chiquvchi ma’lumotlar

Yig’indining qiymatini chiqaring.

Misollar