Thread: prime factorization

There has to be an easier way to find prime factorization rather than just keep on dividing your natural number by prime factors. Does anyone have an equation to find out a way to find your prime factors rather than doing this long way?

Originally Posted by teeplkyl

There has to be an easier way to find prime factorization rather than just keep on dividing your natural number by prime factors. Does anyone have an equation to find out a way to find your prime factors rather than doing this long way?

i don't know of an easier way, but maybe someone else does. usually it is not very long to do it that way. the numbers they ask you to give the prime factorization for are usually relatively small

Originally Posted by teeplkyl

There has to be an easier way to find prime factorization rather than just keep on dividing your natural number by prime factors. Does anyone have an equation to find out a way to find your prime factors rather than doing this long way?

There is an entire area of computational number theory which studies primality testing - that is when we seeking prime factors rather than guessing in a more efficient way. However, this problem is a computationally difficult. Some mathematicians believe it is impossible to find an efficient algorithm because of P versues NP - a problem whose solution is worth one million dollars. The problem is about certain types of algorithms which fall into a category called "NP" computational problem and there is another type of algorithms which fall into a categorty called "P" computational problems. The conjecture asserts that these two categories are completely distinct so if a computational can be solved using NP algorithms then it cannot be solved using P algorithsm, and the other way around too. Now certain algorithms are faster than others. The ones that mathematicians developed for primality testing are not very efficient. Thus, mathematicians fear the sad news that is might be impossible to have efficient algorithms.