вывод, связанный с простыми числами

Ниже написана только функция

Функция простых факторов

void prime(int x) {
    int i, j;

написал это, потому что хотел получить информацию, но у меня ее нет

    for (i = 2; i <= x; i++) {
        if (x % i == 0) {
            for (j = 2; j <= i; j++) {
                if (i == j) {
                    printf("%d", i);
                } else
                if ((i % j) != 0) {
                    printf("%d\n", i);

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

                    goto l;

Здесь оператор goto выходит из цикла if

                } else {
                    break;
                }
            }
        l: 
            x = x / i;
        }
    }
}

Код кажется правильным и также дает простые числа, но факторы не повторяются.

например: 24 вывод должен быть 2,2,3, но вывод идет как 2,3


c factors
person Barry    schedule 05.09.2017    source источник
comment
Сейчас самое время начать учиться пользоваться отладчиком (например, GDB). Кроме того, попробуйте форматировать код более последовательно.   -  person r3mainer    schedule 05.09.2017
comment
Почему на выходе 24 должно быть 2,2,3, а на выходе получается 2,3? 24 = 2 * 2 * 2 * 3, т.е. на выходе должно быть 2,2,2,3.   -  person MiniMax    schedule 05.09.2017

Ответы (2)


arrow_upward
1
arrow_downward

Оператор goto бесполезен, он точно эквивалентен оператору break в вашем случае. Он не выходит из цикла if, он вырывается из цикла for, что и делает break.

Кроме того, внутренний цикл бесполезен: если вы разделите x на i, вы эффективно удалите меньшие простые числа из x, а x % i == 0 останется только для простых значений i.

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

Таким образом, функция может быть упрощена до:

void primefactors(int x) {
    int i;             

    for (i = 2; i <= x;) {
        if (x % i == 0) {
            printf(" %d", i);
            x = x / i;
        } else {
            i++;
        }
    }
    printf("\n");
}

Функцию можно сделать намного быстрее: вы можете остановить сканирование, когда i больше, чем квадратный корень из x:

void primefactors(int x) {
    int i;             

    for (i = 2; i * i <= x;) {
        if (x % i == 0) {
            printf(" %d", i);
            x = x / i;
        } else {
            i += 1 + (i & 1);  // skip even numbers
        }
    }
    printf("%d\n", x);
}
person chqrlie    schedule 05.09.2017
comment
Чем быстрее primefactors(), тем меньше диапазон, так как i*i легко переполняется, когда i > sqrt(INT_MAX). решение подлежит уточнению - person chux - Reinstate Monica; 05.09.2017
comment
Вместо этого предложите for (i = 2; i <= x/i;) {. Попробуйте primefactors(INT_MAX), чтобы увидеть эффект. - person chux - Reinstate Monica; 05.09.2017
comment
@chux: я согласен, что INT_MAX вызывает арифметическое переполнение, но он производит 2147483647 1 после более длительного вычисления, чем обычно. i <= x/i намного медленнее для больших простых чисел. Быстрое грязное исправление было бы for (i = 2; (unsigned)i * i <= (unsigned)x;) { - person chqrlie; 06.09.2017
comment
i <= x/i намного медленнее для больших простых чисел. Возможно нет. Хорошие компиляторы распознают x/i и соседний x%i и выдадут код, который генерирует оба примерно за время, необходимое для одного из них. IOWs, код может получить x/i бесплатно, так как код должен делать x%i. Конечно, код может вызвать проблему с div(). YMMV. - person chux - Reinstate Monica; 06.09.2017
comment
@chux: интересное замечание! Я буду исследовать больше... Я ожидал такой оптимизации, когда и x / i, и x % i вычислялись один за другим, но был очень разочарован в прошлый раз, когда я смотрел на код, сгенерированный как gcc, так и clang. - person chqrlie; 06.09.2017

arrow_upward
0
arrow_downward

Мое решение. Я могу добавить комментарии, если вам нужно.

#include <stdio.h>

void prime_factors(int num) {
    int i = 2;
    while(num > 1) {
        while(num % i == 0) {
            num /= i;   
            printf("%d ", i); 
        }   
        i++;
    }   
}

int main() {
    int num;

    while(1) {
        printf("%s", "Enter the number: ");

        if(scanf("%d", &num) != 1)  
            break;

        // \033[1;31m - changes text color to red
        // \033[0;0m  - resets color back to default
        // It works on Linux, I don't know about Windows.
        if(num <= 1) {
            puts("\033[1;31mThe number must be greater than 1.\033[0;0m");
            continue;
        }   
        puts("Prime factors are:");

        prime_factors(num);

        puts("\n");
    }   

    return 0;
}

Тестирование:

Enter the number: 24
Prime factors are:
2 2 2 3 

Enter the number: 12
Prime factors are:
2 2 3 

Enter the number: 1000
Prime factors are:
2 2 2 5 5 5
person MiniMax    schedule 05.09.2017