Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179


So'ngi izohlar

677. Eratosfen g'alviri
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

: http://im0-tub-ru.yandex.net/i?id=d6600b354647569a5bc5f76513623813&n=24

Eratosfen

Dasturlash boyicha algoritmlarni organib boshlaganlar birinchilardan bolib tub sonlarni topish boyicha Eratosfen galvirini organishadi. Eratosfen galviri tub sonlarni topuvchi effektiv algoritmlardan biri bolib, uning psevdokodi quyidagicha:

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

if A[i] = true:

j := 2i, 3i, 4i, ..., while jn:

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 yigindi bilan ifodalashimiz mumkin:

x sonining butun qismi.

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

 

Kiruvchi malumotlar

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

Chiquvchi malumotlar

Yigindining qiymatini chiqaring.

Misollar

Kiruvchi malumotlar

Chiquvchi malumotlar

1

1

1

2

10

27

3

1000000

13970034

 

Avtor: Azat Yusupov
2015 yil Dasturlash bo'yicha Tatu va uning filiallari talabalari o'rtasida jamoaviy olimpiada. Final. Urgench 21-23 aprel.
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(50) Barcha urinishlar(153)