Minchev

Предложение за решение на задачата за намиране на прости числа от петия междууниверситетски турнир по програмиране от 2002 година.

#include<iostream>
using namespace std;
int main()
{
// Задаване на интервал [a,b] в който се търси броя на простите числа
long long a = 100200300, b = 100300300;

// Брояч на простите числа
long long c = 0;

// Задаване на максималната допъстима грешка
long long MaxErr = ((b – a)*0.1) + 1;

// Ако началото е четно го инкрементираме, т.е. започваме от първото нечетно
if (a%2 == 0) a++;

/*
Цикъл за обхождане на числата в интервала [a,b]
Разглеждат се само нечетни, защото четните не са прости.
Което автоматично редуцира кандидатите в интервала [a,b] наполовина
count = (b – a) / 2
*/
for (long long i=a; i<=b; i+=2)

// Проверка за изключване на всички числа завършващи на 5, още се редуцира броя на кандидатите
if (i%10 != 5)
{
// Булева променлива означаваща че числото е просто (true)
bool isPrime = true;

// За текущия кандидат i се проверява дали се дели на всички числа в интервала [3, i/MaxErr]
// Това действие също редуцира кандидатите
for (long long j=3; j < i/MaxErr; j+=2)
if(i%j == 0)
{
// Ако е така, то числото не е просто.
isPrime = false;
// Следователно можем да прекъснем проверката в интервала [3, i/MaxErr], това също ускорава
break;
}

// Ако е просто инкрементираме брояча
if (isPrime) c++;
}

// Извеждане на броя на простите числа в интервала [a,b]
cout << c << endl;
return 0;
}

Условие на задачата: http://www.math.bas.bg/~nkirov/2002/5cp/prime.html