Thread: Check out factors function

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    68

    Check out factors function

    This function will take a number (n) and give you its prime factorization.

    It runs fine, but I have a sneaking suspicion that there is a more "intuitive" way for the program to take the prime factorization of a negative number--that is, I want the program to be able to factor out a -1 instead of me just printing it.

    Code:
    //Factors.c//Prime Factorization
    
    
    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    
    Primality();
    
    
    //primality function which will determine if a number is prime.
    //long Primality(long n)
    //{
    //check to see if the number is a multiple of 2(ie the number is even) and is not equal to 2
    //	if(n % 2 == 0 && n != 2)
    //	{
    //		return false;  //if the number is even or equal to 2, return false and do not count these numbers
    //	}//end if
    //once we determine that a number is not even or equal to 2, we can check the odds.
    //	for(long i = 3; i * i <= n; i += 2) 
    //	{
    //		if(n % i == 0)
    //		{
    //			return false;
    //		}//end if
    //	}//end for
    //	return true;
    //}//end function primality
    
    
    int main()
    {
    	long n;//user generated number
    	long i;//incrementer
    
    
    	printf("Enter a number to get its prime factorization:  ");
    	scanf("%ld", &n);
    
    
    	//if the number is prime, state so
    	if(Primality(n))
    	{
    		printf("%ld:  This number is prime\n", n);
    	}//end if
    
    
            //if number is negative, take the absolute value of the number, but indicate that       
     //one of the factors of this number is negative 1
            if(n < 0)
            {
                    n = abs(n);
    printf("-1\n");
            }//end if
    
    
    
    
    	//if the number is a composite number
    	else
    	{
    		printf("The Prime factorization of %ld:  \n", n);
    	}//end else
    	
    	//for each potential factor, i
    	for(i = 2; i * i <= n; i++)
    	{
    		//if i is a factor of N, repeatedly divide it out
    		while (n % i == 0)
    		{
    			printf("%ld\n", i);
    			n = n / i;
    		}//end while
    	}//end for
    
    
    	//if the biggest number only occurs once, n > 1
    	if (n > 1) printf("%ld\n", n);
    }//end main

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    That's really hard to read, you must not have copy-pasted as plain text.

    To be mathematically precise, negative numbers can never be prime, and thus, can never have a prime factorization. Prime factorization is only for positive integers. Also, 0 and 1 are neither prime nor composite, so check for that ahead of time. And lastly, prime numbers still have a prime factorization, the only factor being itself.

    However, if you insist on factoring out a -1 if n is negative, try this:
    Code:
    if (n == 0 || n == 1 || n == -1) {
        // 0 and 1 are neither prime nor composite
    }
    
    printf("The prime factorization of %ld \n", n);  // print n in it's original form
    if (n < 0) {
        printf("-1 ");
        n = abs(n);
    }
    ...
    Note, you should only run your while (n % i == 0) loop if i is a prime number.

    For a better method of determining primality, or rather, generating the sequence of prime numbers (good for your "for each potential factor i" loop), look into the Sieve of Eratosthenes.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > if(n < 0)
    Perhaps you should do this before calling Primality(n), not after.

    > That's really hard to read, you must not have copy-pasted as plain text.
    Unfortunately, any attempt to bold/colour/highlight specific lines has the side effect of turning off all the boards code formatting.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by Salem View Post
    Perhaps you should do this before calling Primality(n), not after.
    Meh, I was intending to skip it, since prime numbers still technically have a prime factorization. But yes, if the OP wants special output for primes, it would need to be done before calling Primality(n).

    Quote Originally Posted by Salem View Post
    Unfortunately, any attempt to bold/colour/highlight specific lines has the side effect of turning off all the boards code formatting.
    Ahh yes, I see the printf that is underlined now.

  5. #5
    Registered User
    Join Date
    Jan 2013
    Posts
    68
    Quote Originally Posted by Salem View Post
    > if(n < 0)
    Perhaps you should do this before calling Primality(n), not after.
    Tried that and the out put was a bit funny.

    Code:
    -1
    prime factorization of 97
    97

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Try keeping track of the original value and the absolute value. Then, you can always refer to orig_n if you need to print the original value or check whether it was negative after you do
    Code:
    n = abs(orig_n);

  7. #7
    Registered User
    Join Date
    Jan 2013
    Posts
    68
    Quote Originally Posted by anduril462 View Post
    Try keeping track of the original value and the absolute value. Then, you can always refer to orig_n if you need to print the original value or check whether it was negative after you do
    Code:
    n = abs(orig_n);
    Can you elaborate? I want to try it.

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Read the number from the user and store it in orig_n
    Code:
    long n, orig_n;
    printf("Enter a number to get its prime factorization:  ");scanf("%ld", &orig_n);
    Calculate the absolute value of that
    Code:
    n = abs(orig_n);
    Carry on with your program. Use orig_n for things like checking if the number entered was negative. Use n where you need the positive (absolute) value, i.e. when you want to check primality, find prime factors, etc.

    Basically orig_n can be used to remember the original value the user entered, so you can print it back to the user, and check it for negative to list a -1 in the prime factors, even after you find the absolute value and store it in n.

  9. #9
    Registered User
    Join Date
    Jan 2013
    Posts
    68
    Quote Originally Posted by anduril462 View Post
    Read the number from the user and store it in orig_n
    Code:
    long n, orig_n;
    printf("Enter a number to get its prime factorization:  ");scanf("%ld", &orig_n);
    Calculate the absolute value of that
    Code:
    n = abs(orig_n);
    Carry on with your program. Use orig_n for things like checking if the number entered was negative. Use n where you need the positive (absolute) value, i.e. when you want to check primality, find prime factors, etc.

    Basically orig_n can be used to remember the original value the user entered, so you can print it back to the user, and check it for negative to list a -1 in the prime factors, even after you find the absolute value and store it in n.
    Doing that now, but is there a more intuitive way of factoring negative numbers instead of just printing a negative one?

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by jwall View Post
    Doing that now, but is there a more intuitive way of factoring negative numbers instead of just printing a negative one?
    I still think this whole negative thing is silly. A negative number can't be prime. Thus, a negative number can't have a prime factorization, since at least one factor would have to be negative, and thus that factor, by definition, would not be prime.

    But no, I am not aware of any "magic bullet" answer that will do this all in one or two lines of clean, elegant code. Sometimes the solution just ain't as pretty as you want.

  11. #11
    Registered User
    Join Date
    Jan 2013
    Posts
    68
    Quote Originally Posted by anduril462 View Post
    I still think this whole negative thing is silly. A negative number can't be prime. Thus, a negative number can't have a prime factorization, since at least one factor would have to be negative, and thus that factor, by definition, would not be prime.

    But no, I am not aware of any "magic bullet" answer that will do this all in one or two lines of clean, elegant code. Sometimes the solution just ain't as pretty as you want.
    Yeah, I think this will satisfy anyone who wanted to do prime factorization of any number they wanted.

    Thanks for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function: check if it's a directory
    By Francesco Leone in forum Windows Programming
    Replies: 6
    Last Post: 07-08-2011, 08:22 AM
  2. Function that shows factors
    By coachortiz in forum C Programming
    Replies: 3
    Last Post: 09-29-2010, 11:16 PM
  3. Replies: 3
    Last Post: 02-19-2009, 10:32 PM
  4. function to determine factors of a number
    By lakai02 in forum C Programming
    Replies: 2
    Last Post: 12-18-2002, 03:02 AM