# Thread: factoring... it works for some input

1. ## factoring... it works for some input

I am at a loss... I just can't figure why my program will factor most numbers but some it'll just give out the wrong answer.

2000000009: 7 * 285714287

But I get something else.. please someone help. The problem is in factor().

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int issquare(int i)
{
int j, s;

s = 0;

if(i < 0)
return 0;

j=i&3;

/*weeding out the obvious non squares*/
if((j != 0) && (j != 1))
return 0;

for(j = 1; s < i; j += 2)
s += j;

return (s == i);
}

int isprime(int x)
{
int i;
static long int SmallPrimes[] =
{0,0,1,1,0,1,0,1,0,0};

if (x<10) return SmallPrimes[x];
if (x%2==0) return 0;
if (x%3==0) return 0;
if (x%5==0) return 0;

for (i = 7; i*i<=x; i++)
if (x%i==0) return 0;

return 1;
}

int factor(int c)
{
int r, h, k, s;

if (c % 2 == 0)
return 2;

r = sqrt(c);

if(issquare(c)) {
if(isprime(r))
return r;
else
return factor(r);
}

h = (2 * r) - 1;

if(c % 4 == 1)
k = 5;
else
k = 3;

if(h % 4 != c % 4)
h = h - 2;

s = ((h + k) / 2) * ((2 + h - k) / 2);

while(s != c) {
if(s > c) {
s = s - (2 * k + 2);
k = k + 4;
}
if(s < c) {
h = h + 4;
s = s + (2 * h - 2);
}
}
return((2+h-k)/2);
}

int main(int argc, char **argv)
{
int n, t;
uclock_t start, stop;

n = atoi(argv[1]);

if (argc != 2) {
fprintf(stderr, "\nusage: %s [number]\n", argv[0]);
return -1;
}

if(isprime(n)) {
printf("\n%d is prime\n", n);
return 0;
}

printf("\n%d: ", n);
start=uclock();

while(!isprime(n)) {
t = factor(n);
if (t==0) break;
printf("%d ", t);
n /= t;
}

stop=uclock();
printf("%d", n);
printf("\n\n%.4f seconds\n", (double)(stop-start)/(double) \
UCLOCKS_PER_SEC);

return 0;
}```

2. Your code seems to work for a large number , could you tell me the name of algorithm you have used ?

3. i am using fermat's factorization method, but it's a little different now. hmmm... i wonder what's wrong.

4. Originally posted by skeptik
i am using fermat's factorization method, but it's a little different now. hmmm... i wonder what's wrong.
Thanks for the info.