Как выполнить миллионы вычислений?

Вы не делаете миллионы вычислений, вы делаете их триллионы.

IsPrime будет работать за O (n) раз, то есть будет выполнять 2 миллиона инструкций только для определения этого единственного числа. На то, чтобы потратить два миллиона времени на подобные вещи, потребуется слишком много времени.

Для этого вам действительно нужно использовать что-то вроде: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, который может гораздо более эффективно определять все простые числа в определенном диапазоне.

Сколько времени должно занять выполнение такой программы?

Это полностью зависит от вашей платформы. Я подозреваю, что, поскольку вы выполняете ~ (два миллиона) ^ 2 операций (~ четыре триллиона) вычислений, ужасно долго.

Есть гораздо лучшие способы выполнить то, что вы делаете - например, чтобы проверить простое число, вам нужно проверить только квадратный корень из числа, а не полностью до самого числа. Не говоря уже о том, что, вероятно, существует решение для динамического программирования, которое может сделать это намного быстрее, чем это.

Как говорили другие, это займет много времени. Альтернативный и интересный подход - Сито Эратосфена. Вы можете прочитать об этом по адресу:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Обычно вы инициализируете массив числами 2 ... 2 миллиона. Наименьшее еще не обработанное число - простое. Затем вы удаляете из массива все числа, кратные этому числу, и продолжаете. Он будет работать намного быстрее, чем у вас есть.

Необычный ответ

gotoxy(25,25);

Вы запускаете свою программу в текстовом режиме? Если размер текстового экрана только 80 x 25, и если 25-я строка закрыта какими-то другими вещами, то, скорее всего, вы не увидите никаких изменений на текстовом экране.

Как говорили другие: проверьте пределы своей реализации

Если TurboC++ имеет ‹limits.h›, для этих ограничений реализации есть соответствующий макрос, определенный в этом заголовке.

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

Если это не удается, вам нужно «рассчитать» пределы самостоятельно. Я перехожу на unsigned, потому что у них нет проблем с переполнением, и мне нужно только «вычислить» верхний предел (нижний предел равен 0)

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}

В моей системе первая программа выводит

int goes from -2147483648 to 2147483647.
long goes from -9223372036854775808 to 9223372036854775807.

и 2-й программный выход

unsigned ints go all the way to 4294967295
unsigned longs go all the way to 18446744073709551615

По-прежнему никаких комментариев / ответов о константе, кроме "Epic" ...

#define TWO_MILLION 2*1000*1000

Это плохо. Когда вы измените значение позже, у вас либо будет несоответствие имени и содержания:

#define TWO_MILLION 5*1000*1000

или вы переименуете его в

#define FIVE_MILLION 5*1000*1000

и вам нужно менять его везде, где вы его использовали. Не называйте свои константы после содержимого, это просто превратит ваши магические числа в волшебные имена. Назовите их по их значению, например MAX_NUMBER UPPER_LIMIT RANGE_TO_TEST или как там лучше.

вы также можете использовать методы сита, которые не намного сложнее того, что вы используете. Идея состоит в том, чтобы выбрать первые n последовательных простых чисел и использовать их для построения сита. Я обсуждаю это (с доказательствами) в моем ответе на другой вопрос и Шелдон Л. Купер предоставляет реализацию в своем. Я не думаю, что он получил достаточно голосов за это (у меня уже есть «хороший ответ», так что, возможно, вы могли бы ему помочь в этом.

поэтому после вычисления чисел сита вам нужно только проверить их делимость на числа, которые совпадают с числами сита и меньше квадратного корня из n.

Это может занять очень много времени.

Добавьте это, чтобы увидеть свой прогресс (хотя это займет еще больше времени):

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

Изменить

Как указывают другие, это самый медленный способ подсчета простых чисел. Возможно, цель вашего задания - помочь вам найти (и реализовать) более быстрые?

Ваша программа приводит к целочисленному переполнению, вы можете использовать long long, чтобы исправить это.

Кроме того, ваш алгоритм проверки того, является ли число простым, не очень хорош. Другой не менее простой способ - проверить числа 2 на квадратный корень из числа. Вам нужно только проверить квадратный корень из числа, чтобы определить, является ли оно простым.

Простое изменение покажет вам, насколько быстро ваша программа работает и сколько работы она должна сделать. Ваш статус легко распечатать примерно через каждые 100 итераций. (Или вы можете установить его на 1000 или 10000 итераций.)

Помните, что вы можете УДВОИТЬ скорость вашего цикла за IsPrime.
После того, как вы отметите 2, вам нужно только проверить нечетные числа, и вы можете продвигаться с i+=2 вместо i++.

Если вас беспокоит скорость, почему вы тратите столько времени на проверку четных чисел? (обратите внимание, что как только вы начнете использовать только нечетные числа, вам также нужно будет изменить выходной тест, чтобы он был нечетным числом)

Вы также можете УДВОИТЬ скорость цикла в main, также избегая там четных чисел. (опять же, вам нужно использовать частный случай 2, затем использовать i + = 2, начиная с 3, чтобы получить 3, 5, 7, 9 ....)

Если цикл в IsPrime выполняется вдвое быстрее, а цикл в main - в два раза быстрее, это должно ускорить выполнение вашей программы в 4 раза. (если бы раньше это занимало час, теперь это будет 15 минут.)

Другое большое улучшение скорости, которое вы могли бы сделать, - это запустить цикл только до sqrt(num), а не до num.

Поскольку я ненавижу использовать функции с плавающей запятой, такие как sqrt, я вместо этого предлагаю близкое приближение, которое остановится в пределах 100 итераций прохождения границы sqrt, а также регулярно показываю обновления статуса.

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

P.S. Я поместил этот код в проект на C # (незначительное портирование). Конечно, теперь это работало на 64-битной ОС с улучшенным компилятором и процессором с тактовой частотой 2,8 ГГц.
Он работал менее чем за 20 секунд.