Finding squarefree divisors of a number in C

Question

The requirement is to list all divisors different from 1 of a given number that are not themselves divisible by a perfect square.

Here is my code so far:

#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;
}

If I give input as 20, then I get 1 2 4 5 10 20. I have eliminated all the numbers which are perfect square ie: 4.

Now, I'm having 1 2 5 10 20. Here I don't have to consider 1 that means I'll have 2 5 10 20.

Now, at last, I have to eliminate all those numbers which are divisible by a perfect square, how do I do that?

example: 20 will be eliminated because 4 x 5 = 20 and 4 is a perfect square.

Expected output: 2 5 10

in the result 20 is appearing but 20 = 4*5 and 4 is a perfect square so I have to eliminate all those numbers which have a similar case... — Blogging Bro, Aug 09 '18 at 11:42
Where is 3,7,11,13,17 and 19 went?those neither not perfect square nor divisible by perfect square? — kiran Biradar, Aug 09 '18 at 12:08
those are not the factors of 20... read the description above carefully. — Blogging Bro, Aug 09 '18 at 12:15
You never mention anything about factors. You only mention numbers divisible by a perfect square. — Gerhardh, Aug 09 '18 at 13:29
You have shown some code and some partial description. What is your problem? If your code fails, you need to tell us in which way it fails. — Gerhardh, Aug 09 '18 at 13:30
If you are given a number N and simply want to know if it is square free, you can use this method. For example 20 = 2^2 + 4^2 = 2^2(1+2^2)=2^2*5. So 20 is not square free. https://math.stackexchange.com/questions/3064068/can-the-sum-of-two-squares-be-used-to-determine-if-a-number-is-square-free — user25406, Jan 11 '19 at 00:35

score 0 · Answer 1 · answered Aug 09 '18 at 12:18

You have one evident problem and another possible one.

The evident one is that with

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

you (try to) test whether i is a perfect square, not if it is divisible by a perfect square. That is the reason why your code does not eliminate 20 which is indeed divisible by 4 but is not a perfect square itself.

The possible one if that sqrt returns a double value, and floating point is known to be broken (or more exactly to not always be exact...). So I would not be surprized that your test sometimes returns a wrong result.

What can be done: first round the resul of sqrt instead of (possibly) truncate it: temp = sqrt(i) + .5; And do test whether i is divisible by a perfect square:

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);
}

chqrlie · Accepted Answer · 2018-08-09T18:31:15.797

When you find a divisor i for n, you should remove higher powers of i from n to prevent multiples of powers of i from being found later in the scan:

#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;
}

This algorithm is still quite slow for large primes. A faster method would first find the prime factors in O(sqrt(N)) and print all combinations of the prime factors, but the list would not necessarily be produced in increasing order.

Considering this:

a 32-bit number has at most 9 distinct prime factors:

29!! = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230
there are 2ⁿ - 1 possible combinations of n factors.
all possible prime factors and square free divisors can be collected in rather small arrays, the latter can be sorted and printed.

Here is a much faster version for 32-bit 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-bit int can be supported with a maximum number of prime factors at 15 instead of 9, still acceptable for automatic storage.

Finding squarefree divisors of a number in C

2 Answers2