Поиск квадратичных делителей числа в C

Question

Требуется перечислить все делители, отличные от 1 из данного числа, которые сами не делятся на идеальный квадрат.

Вот мой код до сих пор:

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

int main() {
    int n, i, temp;
    scanf("%d", &n);

    for (i = 1; i <= n; ++i) {
        if (n % i == 0) {
            temp = sqrt(i);
            if (temp * temp != i)
                printf("%d ", i);
        }
    }
    return 0;
}

Если я введу как 20, то я получу 1 2 4 5 10 20, Я исключил все числа, которые являются идеальными квадратными, т.е. 4,

Теперь у меня 1 2 5 10 20, Здесь я не должен учитывать 1 это значит у меня будет 2 5 10 20,

Теперь, наконец, я должен устранить все те числа, которые делятся на идеальный квадрат, как мне это сделать?

пример: 20 будет исключен, потому что 4 х 5 = 20 и 4 является идеальным квадратом.

Ожидаемый результат: 2 5 10

Answer 1

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

#include <stdio.h>

int main() {
    int n, i;

    if (scanf("%i", &n) == 1) {
        for (i = 2; i <= n; ++i) {
            if (n % i == 0) {
                printf("%d ", i);
                while (n % (i * i) == 0)
                    n /= i;
            }
        }
        printf("\n");
    }
    return 0;
}

Этот алгоритм все еще довольно медленный для больших простых чисел. Более быстрый метод сначала найдет простые факторы в O(sqrt(N)) и выведет все комбинации простых факторов, но список не обязательно будет составляться в возрастающем порядке.

Учитывая это:

• 32-битное число имеет не более 9 различных простых факторов:

  29!! = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230

• Есть 2 ⁿ - 1 возможных комбинаций из n факторов.
• все возможные простые множители и квадратные свободные делители могут быть собраны в довольно маленькие массивы, последние могут быть отсортированы и напечатаны.

Вот гораздо более быстрая версия для 32-битной int:

#include <stdio.h>
#include <stdlib.h>

int sort_int(const void *p1, const void *p2) {
    int i1 = *(const int *)p1;
    int i2 = *(const int *)p2;
    return (i1 > i2) - (i1 < i2);
}

int main() {
    int primes[9], divs[1 << 9];
    int i, j, n, p, np, nd;

    if (scanf("%i", &n) == 1) {
        np = 0;
        for (p = 2; p <= n / p; p++) {
            if (n % p == 0) {
                primes[np++] = p;
                while (n % p == 0)
                    n /= p;
            }
        }
        if (n > 1) {
            primes[np++] = n;
        }
        nd = 1 << np;
        for (i = 1; i < nd; i++) {
            divs[i] = 1;
            for (j = 0; j < np; j++) {
                if (i & (1 << j))
                    divs[i] *= primes[j];
            }
        }
        qsort(divs, nd, sizeof(*divs), sort_int);
        for (i = 1; i < nd; i++) {
            printf("%d ", divs[i]);
        }
        printf("\n");
    }
    return 0;
}

64-битный int может поддерживаться с максимальным числом простых факторов в 15 вместо 9 все еще приемлемо для автоматического хранения.

Answer 2

У вас есть одна очевидная проблема и другая возможная.

Очевидным является то, что с

    temp = sqrt(i);
    if(temp*temp != i)

Вы (пытаетесь) проверить i является идеальным квадратом, если он не делится на идеальный квадрат. Вот почему ваш код не устраняет 20, которое на самом деле делится на 4, но само по себе не является идеальным квадратом.

Возможный, если что sqrt возвращает двойное значение, и с плавающей запятой известно, что она не работает (или, точнее, не всегда точна...). Поэтому я не удивлюсь, что ваш тест иногда дает неверный результат.

Что можно сделать: первый раунд результатов sqrt вместо (возможно) обрезать его: temp = sqrt(i) + .5;И сделать ли тест i делится на идеальный квадрат:

if (n%i == 0)
{
    int ok = 1;
    for (temp=2; temp < sqrt(i) + .5; temp++) {
        if (i % (temp * temp) == 0) {
            ok = 0;
            break;
        }
    }
    if (ok) printf("%d ",i);
}