Найти наибольший простой делитель одного целого числа БЕЗ ДЕЛЕНИЯ
Нужен простой наибольший делитель целого числа
!НО по заданию нельзя использовать операции деления ( / и % )
Нужен алгоритм. не пойму от чего отталкиваться.
Ответы (3 шт):
Автор решения: Harry
→ Ссылка
Ну... неэффективно, конечно, но...
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;
}
Автор решения: Qwertiy
→ Ссылка
Не надо недооценивать решето эратосфена: 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
Автор решения: Stanislav Volodarskiy
→ Ссылка
Нельзя делить, значит деление надо написать. Обойдёмся только числами без знака, сложением, вычитанием, неравенствами.
Процедура 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