factoring... it works for some input

This is a discussion on factoring... it works for some input within the C Programming forums, part of the General Programming Boards category; I am at a loss... I just can't figure why my program will factor most numbers but some it'll just ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37

    Angry 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;
    }
    Last edited by skeptik; 10-09-2001 at 02:27 PM.

  2. #2
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Your code seems to work for a large number , could you tell me the name of algorithm you have used ?

  3. #3
    Registered User
    Join Date
    Sep 2001
    Location
    pacific northwest
    Posts
    37
    i am using fermat's factorization method, but it's a little different now. hmmm... i wonder what's wrong.

  4. #4
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 05-08-2009, 09:51 PM
  2. Trouble with a lab
    By michael- in forum C Programming
    Replies: 18
    Last Post: 12-06-2005, 11:28 PM
  3. Determining if input is int, double, or char
    By Lucid003 in forum C++ Programming
    Replies: 4
    Last Post: 11-16-2005, 04:16 PM
  4. EOF messing up my input stream?
    By Decrypt in forum C++ Programming
    Replies: 4
    Last Post: 09-30-2005, 04:00 PM
  5. need help with some input
    By blindleaf in forum C Programming
    Replies: 2
    Last Post: 03-16-2003, 01:50 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21