/* 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
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on December 24th, 2013