C Программа неожиданно замедляется

Question

Простая программа, которую я написал в C, занимает полтора часа для запуска. Я удивлен тем, что C будет так долго работать, потому что из того, что я могу найти в Интернете, C (кроме C++ или Java) является одним из самых быстрых языков.

// this is a program to find the first triangular number that is divisible by 500 factors 

int main() 
{ 
    int a; // for triangular num loop 
    int b = 1; // limit for triangular num (1+2+3+......+b) 
    int c; // factor counter 
    int d; // divisor 
    int e = 1; // ends loop 
    long long int t = 0; // triangular number in use 

    while(e != 0) 
    { 
     c = 0; 

     // create triangular number t 
     t = t + b; 
     b++; 

     // printf("%lld\n", t); // in case you want to see where it's at 
     // counts factors 
     for(d = 1 ; d != t ; d++) 
     {  
      if(t % d == 0) 
      { 
       c++; 
      }  
     } 

     // test to see if condition is met 
     if(c > 500) 
     { 
      break; 
     } 
    } 

    printf("%lld is the first triangular number with more than 500 factors\n", t); 

    getchar(); 
    return 0; 
} 

Предоставленный программа работает через много данных, но ни один из них не всегда сохраняются, только испытания и перешел.

Я использую Tiny C Compiler на Windows 8.

Есть причина, это работает так медленно? Что было бы более быстрым способом достижения такого же результата?

Спасибо!

Answer 1

Вы повторяете более тонны цифр, которые вам не нужны. По определению положительным фактором является любое целое число, которое можно умножить на другое, чтобы получить желаемый продукт.

Ex: 12 = 1*12, 2*6, and 3*4 

Порядок умножения НЕ принимается при определении факторов. Иными словами,

Ex: 12 = 2*6 = 6*2 

Порядок не имеет значения.2 и 6 являются факторами один раз.

Квадратный корень - один синглтон, который выйдет из факторинга продукта, который стоит отдельно. Все остальные попарно, и я надеюсь, что это ясно. Учитывая, что вы можете значительно ускорить свой код, выполнив следующие действия:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

// this is a program to find the first triangular number that is divisible by 500 factors 

int main() 
{ 
    int c = 0;     // factor counter 
    long long int b = 0;  // limit for triangular num (1+2+3+......+b) 
    long long int d;   // divisor 
    long long int t = 0;  // triangular number in use 
    long long int r = 0;  // root of current test number 

    while (c <= 500) 
    { 
     c = 0; 

     // next triangular number 
     t += ++b; 

     // get closest root. 
     r = floor(sqrt(t)); 

     // counts factors 
     for(d = 1 ; d < r; ++d) 
     { 
      if(t % d == 0) 
       c += 2; // add the factor *pair* (there are two) 
     } 
     if (t % r == 0) // add the square root if it is applicable. 
      ++c; 
    } 

    printf("%lld is the first triangular number with more than 500 factors\n", t); 
    return 0; 
} 

Запуск этого on IDEOne.com занимает менее двух секунд, чтобы придумать следующее:

Выход

76576500 is the first triangular number with more than 500 factors 

Надеюсь, это поможет. (и я думаю это правильный ответ). Есть, конечно, более эффективные способы сделать это (see here для некоторых спойлеров, если вам интересно), но идя с вашей идеей кода и видя, насколько далеко мы могли принять это, была цель этого ответа.

Наконец, это находит первое число с БОЛЕЕ 500 факторами (то есть 501 и более) в соответствии с вашим выходным сообщением. Ваш комментарий в верхней части файла указывает, что вы ищете первый номер с 500 или более, что не соответствует вашему выходному сообщению.

Answer 2

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

первый:

while(e!=0) 

как вы объявили e=1, если вы поставите только 1 в цикле он будет работать. Вы не обновляете значение e в любом месте.

Измените это и убедитесь, что он работает нормально или нет.

Answer 3

Без анализа математики:

... 

    do 
    { 
    c = 0; 
    t += b; 
    b++; 

    for (d = 1; d < t; ++d) 
    {  
     if (!(t % d)) 
     { 
     c++; 
     }  
    } 
    } while (c <= 500); 

    ... 

Answer 4

Вы реализуете O алгоритма (п^2). Было бы удивительно, если бы код занял менее полутора часов.

Обратитесь к компьютерной науки учебника для лучшего метода по сравнению с этим методом грубой силы из: проверка 1, 1 + 2, 1 + 2 + 3 и т.д.

Вы можете быть в состоянии сократить внутренний для петля. Действительно ли нужно проверять вплоть до t для факторов, которые делят треугольное число. Например, может ли 10 быть равномерно делимым на любое число, большее 5? или 100 на любое число больше 50?

Таким образом, учитывая число N, какое наибольшее число может равномерно делить N? Продолжайте читать/изучать эту проблему.

Кроме того, как другие люди уже упоминалось, внешний контур может быть просто закодирован как:

while (1) 
    { 
    // etc. 
    } 

Таким образом, нет необходимости нужно объявить e или a? Обратите внимание, что это не влияет на продолжительность времени, но ваш стиль кодирования указывает, что вы все еще учитесь, и, таким образом, рецензент будет подвергать сомнению все, что делает ваш код!

Answer 5

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