Решение задачи №36 «Постулат Бертрана» с ACMP
Условие задачи
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.
Напомним, что число называется простым, если оно делится только само на себя и на единицу.
Входные данные
Входной файл INPUT.TXT содержит целое число n (2 ≤ n ≤ 50000).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.
Решение на C++
#include <iostream>
using namespace std;
int main(){
int t,n,i,k,p=0,l;
cin>>n;
bool S[2*n];
for(k=0; k<=n*2; ++k)
S[k]=true;
for(k=2; k*k<=n*2; ++k)
if(S[k]) for(l=k*k; l<=2*n; l+=k) S[l]=false;
for(k=n+1; k<=n*2; ++k)
if(S[k]) p++;
cout<<p;
return 0;}
Условия задач взяты с сайта acmp.ru