Предложение за решение на задачата за намиране на прости числа от петия междууниверситетски турнир по програмиране от 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
