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

Question

Мой код наклеивается below.When я запустить эту программу, она продолжает calculating.I я использую старый Turbo C++ compiler.How много времени, если такая программа предпринять, чтобы выполнить? Я ждал около 5 минут, но там не было вывод.

/*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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

затактовой ответ

gotoxy(25,25);

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

Answer 6

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

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

Answer 7

Простое изменение покажет вам, как быстро работает ваша программа и сколько работы она должна выполнить. Легко распечатать свой статус примерно каждые 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 8

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

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

Answer 9

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

Если 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; 
} 

---

В моей системе, 1-й программных мероприятий

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

и вторая программа выводит

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

Answer 10

Еще нет комментариев/ответ о й e, за исключением «Epic» ...

#define TWO_MILLION 2*1000*1000 

Это плохо. При изменении значения позже, вы либо имя-контент-несоответствие:

#define TWO_MILLION 5*1000*1000 

или переименовать его в

#define FIVE_MILLION 5*1000*1000 

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