# squarerootconstraints.halleck.c:

```/* Factoring by square root constraint. */
#include <stdio.h>

long N, S, R, P, Q, A, D, T;

/* Integer square root by Halleck's method, with Legalize's speedup */
/* Modified to leave remainder */
long remainder;
long isqrt (x) long x;{
long   squaredbit, root;
if (x<1) return 0;
squaredbit  = (long) ((((unsigned long) ~0L) >> 1) &
~(((unsigned long) ~0L) >> 2));
/* Form bits of the answer. */
remainder = x;  root = 0;
while (squaredbit > 0) {
if (remainder >= (squaredbit | root)) {
remainder -= (squaredbit | root);
root >>= 1; root |= squaredbit;
} else { root >>= 1; }
squaredbit >>= 2;
}
return root;
}

main () {
printf ("Number to factor?\n");
scanf  ("%ld", &N); printf ("N = %ld\n", N);
if (N < 0) {
printf ("Number must be positive\n");
return -1;
} else if (N == 0) {
printf ("0 is a factor\n");
return 0;
}
S = isqrt(N);
if (remainder == 0) {
printf ("%ld is a factor\n",S);
return S;
}
R = N - S*S;
for (D=1; 1; D++) {
T = isqrt (D*D + 2*S*D - R);
if (remainder == 0) {
A = T - D;
P = S - A;
printf ("%ld is a factor\n",P);
return P;
}
}
}

```

# Go to ...

```This page is http://www.cc.utah.edu/~nahaj/factoring/squarerootconstraints.halleck.c.html