Нужен простой наибольший делитель целого числа
!НО по заданию нельзя использовать операции деления ( /
и %
)
Нужен алгоритм. не пойму от чего отталкиваться.
Нужен простой наибольший делитель целого числа
!НО по заданию нельзя использовать операции деления ( /
и %
)
Нужен алгоритм. не пойму от чего отталкиваться.
Ну... неэффективно, конечно, но...
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;
}
Не надо недооценивать решето эратосфена: 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
Нельзя делить, значит деление надо написать. Обойдёмся только числами без знака, сложением, вычитанием, неравенствами.
Процедура 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