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