2

Нужен простой наибольший делитель целого числа

!НО по заданию нельзя использовать операции деления ( / и % )

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

14
  • 2
    Генерируй простые числа решетом. Используй сложение и вычитание. А потом проверяй на делимость точно так же сложением и вычитанием. Ну и используй ускоренные методы проверки на делимость для малых простых.
    – Akina
    Commented 9 июн. 2022 в 8:30
  • Реализуйте свои операции деления и остатка от деления без использования библиотечных, и потом используйте их в стандартном алгоритме. Commented 9 июн. 2022 в 8:36
  • ничего не понял. каким решетом? какие ускоренные методы? Commented 9 июн. 2022 в 8:52
  • А диапазон значений этого самого целого числа?
    – Harry
    Commented 9 июн. 2022 в 10:52
  • @Akina, про решето согласен, а вот проверка делимости тут лишняя.
    – Qwertiy
    Commented 9 июн. 2022 в 11:22

3 ответа 3

3

Ну... неэффективно, конечно, но...

int MaxFactor(int N)
{
    if (N < 2) return -1;  // некорректное значение
    vector<int> v(N+1,0);
    for(int k = 2; k <= N; ++k)
    {
        if (v[k]) continue;
        for(int m = k*2; m <= N; m += k)
            v[m] = k;
    }
    return v[N] ? v[N] : N;
}

Ой, не глянул, что С... Тогда

int MaxFactor(int N)
{
    if (N < 2) return -1;  // некорректное значение
    int * v = calloc(N+1,sizeof(int));
    for(int k = 2; k <= N; ++k)
    {
        if (v[k]) continue;
        for(int m = k*2; m <= N; m += k)
            v[m] = k;
    }
    N = v[N] ? v[N] : N;
    free(v);
    return N;
}
10
  • Ой.. У тебя почти тот же алгоритм, что и у меня...
    – Qwertiy
    Commented 9 июн. 2022 в 11:24
  • А в чём неэффективность? Ваш алгоритм на один децл медленнее линейного. Commented 9 июн. 2022 в 11:34
  • 2
    @StanislavVolodarskiy, неэффективность в том, что ради одного числа мы жрём кучу памяти (причём с выделением и освобождением) и делаем довольно затратные вычисления, когда просто цикл с делением отработал бы куда быстрее. А вот если бы надо было посчитать для многих чисел, то такой алгоритм с однократным расчётом таблицы и мгновенными ответами был бы эффективнее.
    – Qwertiy
    Commented 9 июн. 2022 в 11:41
  • @StanislavVolodarskiy А не ближе к O(N^2)? Что-то не могу сообразить, внешний цикл - O(N), но для каждого простого еще один цикл... O(N^2) не дотягивает, но O(N lg N) перекрывает, нет? Ну и по памяти — O(N).
    – Harry
    Commented 9 июн. 2022 в 11:41
  • @StanislavVolodarskiy, кстати, асимптотика тут O(n*lb(n)), а не линейная.
    – Qwertiy
    Commented 9 июн. 2022 в 11:42
2

Не надо недооценивать решето эратосфена: tio.run

#include <stdio.h>

#define MAXN 1048576

unsigned d[MAXN] = {0, 1};

int main()
{
  for (unsigned x=2; x<MAXN; ++x)
    if (!d[x])
      for (unsigned q=x; q<MAXN; q+=x)
        d[q] = x;

  for (unsigned q=1; q<MAXN; q*=100)
    for (unsigned w=0; w<16; ++w)
      printf("%u - %u\n", q+w, d[q+w]);

  return 0;
}
1 - 1
2 - 2
3 - 3
4 - 2
5 - 5
6 - 3
7 - 7
8 - 2
9 - 3
10 - 5
11 - 11
12 - 3
13 - 13
14 - 7
15 - 5
16 - 2
100 - 5
101 - 101
102 - 17
103 - 103
104 - 13
105 - 7
106 - 53
107 - 107
108 - 3
109 - 109
110 - 11
111 - 37
112 - 7
113 - 113
114 - 19
115 - 23
10000 - 5
10001 - 137
10002 - 1667
10003 - 1429
10004 - 61
10005 - 29
10006 - 5003
10007 - 10007
10008 - 139
10009 - 10009
10010 - 13
10011 - 71
10012 - 2503
10013 - 31
10014 - 1669
10015 - 2003
1000000 - 5
1000001 - 9901
1000002 - 166667
1000003 - 1000003
1000004 - 89
1000005 - 409
1000006 - 71429
1000007 - 34483
1000008 - 43
1000009 - 3413
1000010 - 9091
1000011 - 333337
1000012 - 19231
1000013 - 383
1000014 - 166669
1000015 - 200003
0
2

Нельзя делить, значит деление надо написать. Обойдёмся только числами без знака, сложением, вычитанием, неравенствами.

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

Функция max_prime_factor выполняет обычное разложение целого на простые. Само разложение выбрасывается, возвращается только максимальный простой делитель. Переменная i2 хранит квадрат i. Умножение запрещено (мною), поэтому квадрат считаем отдельно через сложения.

Что возвращать для n = 1 не очень понятно. Задание требует вернуть максимальный простой множитель, а таковых у единицы нет вовсе.

В функции main есть деления и умножения, но это тестовый код. Его тоже можно переписать, но, кажется, это немного слишком. :)

Решение требует логарифмической памяти от n. Работает за время sqrt(n)log(n):

#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>

void divmod(uint64_t a, uint64_t b, uint64_t *div, uint64_t *mod) {
    if (a < b) {
        *div = 0;
        *mod = a;
        return;
    }
    divmod(a, b + b, div, mod);
    *div += *div;
    if (*mod >= b) {
        *mod -= b;
        ++*div;
    }
}

uint64_t max_prime_factor(uint64_t n) {
    uint64_t i = 2;
    uint64_t i2 = 4;
    uint64_t max_prime_factor = 0;

    while (i2 <= n) {
        uint64_t div;
        uint64_t mod;
        divmod(n, i, &div, &mod);
        if (mod == 0) {
            max_prime_factor = i;
            do {
                n = div;
                divmod(n, i, &div, &mod);
            } while (mod == 0);
        }
        i2 += i + i + 1;
        ++i;
        if (i > 3) {
            i2 += i + i + 1;
            ++i;
        }
    }
    if (n > max_prime_factor) {
        max_prime_factor = n;
    }
    return max_prime_factor;
}

int main() {
    for (uint64_t m = 1; m <= UINT64_MAX / 10U - 10; m *= 10U) {
        for (uint64_t n = m; n < m + 10; ++n) {
            printf("%" PRIu64 " - %" PRIu64 "\n", n, max_prime_factor(n));
        }
    }
}
$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -O3 temp.c

$ time ./a.out 
1 - 1
2 - 2
3 - 3
4 - 2
5 - 5
6 - 3
7 - 7
8 - 2
9 - 3
10 - 5
10 - 5
11 - 11
12 - 3
13 - 13
14 - 7
15 - 5
16 - 2
17 - 17
18 - 3
19 - 19
100 - 5
101 - 101
102 - 17
103 - 103
104 - 13
105 - 7
106 - 53
107 - 107
108 - 3
109 - 109
1000 - 5
1001 - 13
1002 - 167
1003 - 59
1004 - 251
1005 - 67
1006 - 503
1007 - 53
1008 - 7
1009 - 1009
10000 - 5
10001 - 137
10002 - 1667
10003 - 1429
10004 - 61
10005 - 29
10006 - 5003
10007 - 10007
10008 - 139
10009 - 10009
100000 - 5
100001 - 9091
100002 - 2381
100003 - 100003
100004 - 1087
100005 - 113
100006 - 1613
100007 - 1031
100008 - 463
100009 - 157
1000000 - 5
1000001 - 9901
1000002 - 166667
1000003 - 1000003
1000004 - 89
1000005 - 409
1000006 - 71429
1000007 - 34483
1000008 - 43
1000009 - 3413
10000000 - 5
10000001 - 909091
10000002 - 35461
10000003 - 769231
10000004 - 18797
10000005 - 666667
10000006 - 563
10000007 - 10627
10000008 - 138889
10000009 - 434783
100000000 - 5
100000001 - 5882353
100000002 - 1187
100000003 - 155521
100000004 - 5101
100000005 - 952381
100000006 - 101833
100000007 - 100000007
100000008 - 154321
100000009 - 671141
1000000000 - 5
1000000001 - 52579
1000000002 - 3943
1000000003 - 141623
1000000004 - 148721
1000000005 - 66666667
1000000006 - 500000003
1000000007 - 1000000007
1000000008 - 167
1000000009 - 1000000009
10000000000 - 5
10000000001 - 27961
10000000002 - 1666666667
10000000003 - 1428571429
10000000004 - 2500000001
10000000005 - 666666667
10000000006 - 33557047
10000000007 - 189613
10000000008 - 1298027
10000000009 - 295081
100000000000 - 5
100000000001 - 8779
100000000002 - 1543067
100000000003 - 100000000003
100000000004 - 1422637
100000000005 - 215659
100000000006 - 12667849
100000000007 - 283286119
100000000008 - 462962963
100000000009 - 10477
1000000000000 - 5
1000000000001 - 99990001
1000000000002 - 166666666667
1000000000003 - 1152763
1000000000004 - 501001
1000000000005 - 66666666667
1000000000006 - 117674747
1000000000007 - 28969553
1000000000008 - 8331667
1000000000009 - 519217
10000000000000 - 5
10000000000001 - 1058313049
10000000000002 - 328121
10000000000003 - 48492137
10000000000004 - 357142857143
10000000000005 - 6605827
10000000000006 - 6326063
10000000000007 - 13901
10000000000008 - 6038647343
10000000000009 - 3049927
100000000000000 - 5
100000000000001 - 121499449
100000000000002 - 746079353
100000000000003 - 276964579
100000000000004 - 46904315197
100000000000005 - 159234401
100000000000006 - 65983
100000000000007 - 1012201
100000000000008 - 258233
100000000000009 - 8705453
1000000000000000 - 5
1000000000000001 - 9091
1000000000000002 - 166666666666667
1000000000000003 - 67103479
1000000000000004 - 385248971
1000000000000005 - 50867
1000000000000006 - 27031410499
1000000000000007 - 360620266859
1000000000000008 - 833316667
1000000000000009 - 322459
10000000000000000 - 5
10000000000000001 - 69857
10000000000000002 - 1289733131
10000000000000003 - 1428571428571429
10000000000000004 - 50010001
10000000000000005 - 37884167
10000000000000006 - 139449433
10000000000000007 - 5396507
10000000000000008 - 138888888888889
10000000000000009 - 4332288241
100000000000000000 - 5
100000000000000001 - 21993833369
100000000000000002 - 594085421
100000000000000003 - 100000000000000003
100000000000000004 - 1246820607451
100000000000000005 - 2929595521
100000000000000006 - 3743297
100000000000000007 - 592951213
100000000000000008 - 22278185023
100000000000000009 - 84530853761623
1000000000000000000 - 5
1000000000000000001 - 999999000001
1000000000000000002 - 52445056723
1000000000000000003 - 1000000000000000003
1000000000000000004 - 562425889
1000000000000000005 - 2187161
1000000000000000006 - 77724234416291
1000000000000000007 - 729644203597
1000000000000000008 - 166667
1000000000000000009 - 1000000000000000009

real  2m33.545s
user  2m32.512s
sys   0m0.020s

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.