Разложение на множители

[_Gleb_]

Пытаюсь написать код, который раскладывал бы длинное целое число n1 на множители: в нулевой строке массива table должны располагаться сами множители, а в первой -- степени при них. Помогите, пожалуйста, разобраться, что неправильно:

Код: Выделить всё

      int table[20][2];
      int i1, i2;
      i1=1;
      i2=2;
        while (i2<=n1) {
          table[i1][1]=0;
            if (n1%i2==0) {
              table[i1][0]=i2;
                while (n1%i2==0) {
                  table[i1][1]++;
                  n1=n1/i2;
                }
              i1++;
            }
          i2++;
        }
      table[++i1][0]=0;

[drBatty]

индексы считают от нуля.

Код: Выделить всё

int main()
{

   int table[20][2];
   int i1, i2;
   i1=0;
   i2=2;
   int n1 = 126712*29*128;
   while (i2<=n1) {
       table[i1][1]=0;
       if (n1%i2==0) {
           table[i1][0]=i2;
           while (n1%i2==0) {
               table[i1][1]++;
               n1=n1/i2;
           }
           i1++;
       }
       i2++;
   }
   table[i1][0]=0;
   for(i1 = 0; table[i1][0]; i1++)
       printf("%d^%d\t",table[i1][0], table[i1][1]);
   printf("\n");
   return 0;
}

[_Gleb_]

У Кернгана и Ритчи написано, то иногда имеет смысл пожертвовать нулевым столбиком в пользу большей понятности. Я так и сделал. А код какую-то полную лажу выдаёт.

[sarutobi]

хм.... неплохая разминка для мозгов.... вот так такая задачка решается правильно:

Код: Выделить всё

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

int main()
{

    int table[20][2];
    int i1, i2;
    i1=0;
    i2=2;
    int n1 = 126712*29*128;
    int n2 = sqrt(n1) +1;

    while (i2 <= n2) {
        table[i1][1]=0;
        if (n1%i2==0) {
            table[i1][0]=i2;
            while (n1%i2==0) {
                table[i1][1]++;
                n1=n1/i2;
            }
            i1++;
        }
        i2 += (i2 == 2) ? 1 : 2;
    }
    table[i1][0]=0;
    for(i1 = 0; table[i1][0]; i1++)
    printf("%d^%d\t",table[i1][0], table[i1][1]);
    printf("\n");
    return 0;

[drBatty]

иногда имеет смысл пожертвовать нулевым столбиком в пользу большей понятности. Я так и сделал

предупреждать надо.

А код какую-то полную лажу выдаёт.

Чей, я свой проверил,
sarutobi, наверно тоже не из пальца высосал. У него и лучше намного. А у меня как у вас, такой же тупой, но правильный, ищите различия

PS:
числа для проверки можно получать не только так:
i2 += (i2 == 2) ? 1 : 2;
но и так:
static int i3 = 4;
i2 += (i2 == 2) ? 1 :
(i2 == 3) ? 2 : (i3 = i3^6);
первый способ даёт
2 3 5 7 9 11 13 15 17 19 21 23 25... Все нечётные
второй
2 3 5 7 11 13 17 19 23 25... Все нечётные не кратные 3

Если известно частное, намного быстрее вычислить остаток так:
z = x / y;
t = x - z * y;//остаток.

PPS: Внутренний цикл надо заменить на do{}while();

Код: Выделить всё

            int tmp;
            do{
                table[i1][1]++;
                tmp=n1;
                n1 /= n2;
            }(while(tmp - n1 * n2 == 0);

[promov]

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

Код: Выделить всё

      int table[20][2];

Непонятно. А что обозначают переменные, значениями которых заполняются строки со второй по 19-ю ? Я так понял, в массиве мы должны заполнить две строки- нулевую и первую. А остальные 18?

[_Gleb_]

Погодите. Для определённости: table[столбец][строка]. В этой части кода заполняются первая и вторая строки. Я так имел в виду. Боюсь, что в приведённом куске всё правильно. А где-то далее по ходу программы нулевая строка перебивается другими значениями. И я не могу понять, где!

[_Gleb_]

Всё, не могу. Я на грани истерики. До вот этих строк:

Код: Выделить всё

for (i1=1; table[i1][0]!=0; i1++) {
          table[i1][2]=0;
              while ((n2%table[i1][0]==0) && (table[i1][2]<table[i1][1])) {
                table[i1][2]++;
                n2=n2/table[i1][0];
              }
        }

нулевая строка table заполнена правильно. После этого что-то перебивает значения элементов в этой строке. Почему это происходит?

[promov]

Всё, не могу. Я на грани истерики. До вот этих строк:
[code][code]
нулевая строка table заполнена правильно. После этого что-то перебивает значения элементов в этой строке. Почему это происходит?

Это може происходить по чему угодно. В том числе и по этой причине.

Погодите. Для определённости: table[столбец][строка].

Должно быть [cтрока][столбец], Глеб...

Я бы на твоём месте начал писать код заново.

[_Gleb_]

Но 7 строк!!! и перед ними значения правильные, а после -- какие-то левые. В этом куске строках значения, понятное дело, нигде меняться не должны. Я не могу представить, что можно написать принципиально нового вместо этих 7 строк.

[Folderx]

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

А как ты это учитываешь при инициализации массива ?

Код: Выделить всё

int table[20][2];
      int i1, i2;
      i1=1;
      i2=2;
        while (i2<=n1)

Где n1 ?

[_Gleb_]

Разобрался. Дело было в том что, я неправильно задал массив table. А "особо дружественный" компилятор проглотил все попытки записать в несуществующую строку массива и ничего не сказал.

[KiWi]

Разобрался. Дело было в том что, я неправильно задал массив table. А "особо дружественный" компилятор проглотил все попытки записать в несуществующую строку массива и ничего не сказал.

У массивов нет "несуществующих" строк -- массив -- лишь offset'ы в памяти.

[cheer]

пиши на java, будет тебе сразу ArrayOutOfBoundsException

[drBatty]

А "особо дружественный" компилятор проглотил все попытки записать в несуществующую строку массива и ничего не сказал.

Это не компилятор. Это стандарт языка Си такой. И это не баг, а фича. Сделано это для того, чтобы не тратить время на ненужные проверки.
Если написано на Си

Код: Выделить всё

#define N 20

int m[N];
int j;
for(j = 0; j < N; j++) m[j] = 0;

В данном случае проверка не нужна, ведь тело цикла выполнится только если j < N, кроме того, j никак не сможет стать меньше нуля, ведь она только увеличивается. А в java пришлось бы проверять условие 2 раза(в этом случае). Выбирайте сами, что для вас важнее: защита от собственной дурос невнимательности, или скорость и компактность.

[drBatty]

Всё, не могу. Я на грани истерики. До вот этих строк:

Надо не в истерике биться, а использовать дебагер. Или(если религия не позволяет), просто распечатать, что там происходит(в данном случае содержимое массива). А потом пролистать(или распечатать) вывод программы.

[cheer]

Э? Какое условие пришлось бы проверять в java, причём два раза? Насчёт компактности:

Код: Выделить всё

for (int j = 0; i < N; i++)

компактнее, чем

Код: Выделить всё

int j;
for (j = 0; i < N; i++)

[drBatty]

Э? Какое условие пришлось бы проверять в java, причём два раза? Насчёт компактности:

Код: Выделить всё

for (int j = 0; i < N; i++)

компактнее, чем

Код: Выделить всё

int j;
for (j = 0; i < N; i++)

Внимательнее пожалуйста. Во первых не путаем i и j, во вторых в некоторых компиляторах(при некоторых настройках) первый вариант не пройдёт, в третьих int j; всего лишь объявление, и не порождает кода(если это встроенный тип, вроде int), в четвёртых, это разный код, если есть разница в области видимости j.
Почему я использовал более длинную запись(но не более длинный/дорогой код!):
1) Более переносимо вниз, к старым компиляторам/стандартам.
2) Возможность использовать j после цикла.

По поводу проверок: проверка внутри условия цикла дублирует проверку выхода за границу массива, очень частый, но не обязательный случай. Сомневаюсь, что компилятор языка типа java уберёт дублирующую проверку в данном случае, и уверен, что с этим не справится интерпретатор. Проверку выхода левее нуля не уберёт не тот не другой, в этом я почти уверен. В итоге, простенький цикл выполнится в 5-500 раз быстрее на С/С++ чем на java. Нужны тесты?

[cheer]

ага, тесты нужны. Как вычислять время в миллисекундах в C, кроме разность двух clock(), делённая на CLOCKS_PER_SEC?

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

[drBatty]

ага, тесты нужны. Как вычислять время в миллисекундах в C

Ассемблерными вставками можно?

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

ну если речь не шла о совместимости и о времени жизни j, то в моём компиляторе допустимы обе записи.
PS Мы чего-то отдалились от темы... Может открыть топик: что быстрее и компактней C или java? Но не здесь.

[cheer]

если ассемблерными вставками, то тогда сравнить будет невозможно. А так - если клоками, то цикл на java до 10'000'000 за 22 мс проходит, а на C - за 60.

[sarutobi]

drBatty
>По поводу проверок: проверка внутри условия цикла дублирует проверку выхода за границу массива, очень частый, но не обязательный случай. Сомневаюсь, что компилятор языка типа java уберёт дублирующую проверку в данном случае, и уверен, что с этим не справится интерпретатор.
Насчет интерпритаторов не уверен, может быть действительно оставят - от языка зависит сильно. javac проверок вообще делать не будет - платформа обязана выбросить ArrayIndexOutOfBoundException при уходе как влево так и вправо.

[drBatty]

платформа обязана выбросить ArrayIndexOutOfBoundException при уходе как влево так и вправо.

Да? А я не знал.
В таком случае будет работать примерно одинаково быстро.