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

Question

Мой код вставлен ниже. Когда я запускаю эту программу, она продолжает вычислять. Я использую старый компилятор Turbo C ++. Сколько времени должна занять выполнение такой программы? любой вывод.

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

Answer 1

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

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

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

Answer 2

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

gotoxy(25,25);

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

Answer 3

Как уже говорили другие, это займет много времени.Одним из альтернативных и интересных подходов является сито Эратосфена.Вы можете прочитать об этом:Наименьшее число, еще не обработанное, является простым.Затем вы удаляете все кратные этого числа из массива и продолжаете.Он будет работать намного быстрее, чем у вас.

Answer 4

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

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

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

Answer 5

Все еще нет комментариев / ответов о константе, кроме "Эпического" ...

#define TWO_MILLION 2*1000*1000

Это плохо. Когда вы позже измените значение, у вас возникнет несоответствие name-content:

#define TWO_MILLION 5*1000*1000

или вы переименовали его в

#define FIVE_MILLION 5*1000*1000

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

Answer 6

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

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

#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;
}

---

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

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

Answer 7

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

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

Answer 8

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

---

Признайте, что вы можете DOUBLE скорость вашего цикла в IsPrime.
После того, как вы проверите 2, вам нужно только проверить нечетные числа, и вы можете перейти с i+=2 вместо i++.

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

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

Если цикл в IsPrime выполняется в два раза быстрее, а цикл в main - в два раза быстрее, это должно ускорить вашу программу на 4X . (если бы это заняло час раньше, сейчас это займет 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 секунд.

Answer 9

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

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

Answer 10

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

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

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

Редактировать

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