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

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.

> 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.

Originally Posted by Salem

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).

Originally Posted by Salem

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.

Originally Posted by Salem

> 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

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

Originally Posted by anduril462

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.

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.

Originally Posted by anduril462

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?

Originally Posted by jwall

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.

Originally Posted by anduril462

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.