How can I factor large numbers into their prime form?

[Krazie]

Would someone PLEASE help me. This is very basic, so I know this will be simple to you guys. I need to know how to break a random composite number down into its simplest prime form. Like 4=2 squared. Or like 12=3*2. I need to know how to make up larger composite numbers out of their most basic primes. Someone please help me. I have a test in on monday about this.

 

[Krazie]

Come on guys. Please help me with this one. Like how would I find the prime factorization for the number 2343?

 

[Hurkyl]

Try guessing a prime factor; there are only a dozen or two possibilities for such a small number.

 

[arivero]

I asked the same to my students in the previous exam... do you live in Teruel? Anyway, try to decompose the problem in two smaller ones. A function telling you if a given number is prime, and then a sort of loop dividing the original number until it reduces to the unity.

 

[abertram28]

if you start by dividing the number by two youll know what number the primes must lie below.

you could use brute force on the problem with a calculator and a list of known prime numbers less than 2344/2.

http://www.utm.edu/research/primes/lists/small/1000.txt this is a list of the first 1000 primes. you can use a calculator and start with the ones just less than 1172. if you find its divisible by 3 (add the digits to create a new number, then add the digits until you get a number you know is divisible by 3, like if you had 1234 youd add 1+2+3+4=10 which you know is not divisible by 3. if it is divisible by 3, then the result of dividing by 3 is also a factor. you can then factor the smaller number)


although kinda tedious, direct testing is the best way for smaller numbers.

start with 2,3,5. that will be easier. youll get to a point where youll have either a 2,3,5 or 7 and

2343 is divisible by 3. 2+3+4+3=12 1+2=3. ! so take 3 out.
2343/3 and 3 are factors. since three is prime, throw it in the prime factors.

so you have 781. you can cross check to see if 781 is prime with that link i gave. 781 isn't in that list, so begin by dividing by 7, since you can see its not a 2, 3, or 5. go up from there dividing with your calculator by prime numbers. if you get one, put the number in the prime factors list and continue.

i don't want to spoil the fun... but there are "factorizers" (programs to factorize or prime factor numbers) with the original or my personal favorite being the one that made the name. ill tell you it only finds 3, so from there, its up to you. the limit on the program i use is like 2.1 billion. after that, your on your own :p

 

[hello3719]

hehe too bad factorization is an NP problem,lets still have hope that there is a way to factorize without trial and error.

 

[cookiemonster]

One quick note: you really don't need to go up to n/2. The largest possible factor would be \lfloor \sqrt{n} \rfloor, particularly in the case of a perfect square.

If you have a programmable calculator, it's not hard to write a program to just test all odd numbers starting from 3. As long as the number's not too big, it's okay... And you don't have to store the list of primes.

cookiemonster

 

[abertram28]

there are plenty of ways.
make a simple computer program.
take n = the number you want to factorize.
begin by taking n/i=a. put i=2 to start (because n/1=n). test if a is whole.
if a is not whole, add one to i. retest. (to test if a is whole, test int(a)-a=0)
if a is whole, store i as a prime factor.
start over, putting n = (original n)/i
repeat until i=n
order list of prime factors from smallest to greatest. if a factor, i, is repeated, take i^j, where j is the number of times its repeated.
end.

instead of checking the list of prime factors for repeats, you can just test when you find that n/i is whole, you can then take n/(i*m) with m equaling the n/i to start and decreasing by 1 each iteration. the first number for which n/(i*m) is whole gives you i^m as a prime factor. you can then continue the prime factorization with n/(i*m)

similarly you can start the test of division at n/i with i=n-1 and then re factorize all factors you find until all are tested. this isn't much of a reorganization.

you can port that to any language you like based on the fact that its not even unicode, let alone comprehensable.

but is that really a simpler way? btw, ill admit that there are plenty of ways that are faster with computers, but that's the simplest to understand and the most basic, and it should work all the time. i wanted it to be simple so the person who orginally asked the question would be able to follow along. you could easily put in a list of prime numbers for i, so that i can't bother to be useless numbers. but its not necessary for the simplest way to find the prime factorization. it is said by many that prime factorization is most easily done by hand for small numbers.

according to the bible of math forums (/sarcasm)
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
says that the best so far is the pollard strassen method.
2343 is small though, comparitively. the method is also far too complex to bother with for such a small number.

 

[cookiemonster]

You can skip every even number except for 2. So you can increment by 2's starting from 3 as long as you take all the 2's out of the number yourself, which is easy enough.

cookiemonster

 

[abertram28]

you can skip any integer multiple of a prime number actually.
in fact, like i said, you only have to test prime numbers.
thats kinda the whole point.
you divide by the smallest prime number, and if its not whole, you divide by the next smallest one. continue until you reach your number or you find a factor. if you find a factor, start over at 2 and divide until you get a whole number. is that any different from what i said before?

my computer way requires no prior knowledge of whether a number is prime. that is another problem in its own, which is why i avoided it and provided a link to a prime list.

 

[abertram28]

also, what you were saying, reducing the numbers you test for divisiblity by...
well, basically you were saying that you want to simplify the number manually before using the computer, and what i was saying is that for this number and numbers of its size, its much easier to just use the hand method with the list of prime numbers.

using your method you wouldn't only skip the even numbers, but also multiples of 3. and 5s. you didnt list those, and i assume its because there are nearly an infinite number of reductions as the number gets larger. you can just add lines for the easy factors, like all the evens. just test for divide by 2 first, then go by 3,5,7,9... but obviously you want to have about 5 lines first. first one says if its even. second one sums the digits until a single digit, then tests to see if its 3,6,9... third would be to see if it ends in 5. this leads to a basic table of prime numbers though, and doesn't do much functionally but reduce a few numbers from being tested. it was more simple on the calculator for larger numbers, but probably insignifigant for realistic numbers. basically, the programs would do the same thing. only mine would be more simply written and require a few extra cycles to complete. more simply written was to be more simply understood. it must be accepted that there are tons of things you can do to reduce the calculation time, but none of them compares to having a list of the primes less than your number/2. you then iterate using i as a list of given primes in your TI or whatever for your casio.

lets also assume without a calculator and a list of primes the person would have trouble since the largest prime factor isn't that small. anyhow, your square root of x as a limit on the factor size would apply in most cases, but some programs wouldn't be written so gracefully and therefore wouldn't list all prime factors properly. someone might program it wrong and leave out the factors higher than the sq. root x. of course, they would almost always forget to save the last factor in that case... but still.

 

[cookiemonster]

Why would you use n/2...? The factors come in pairs. All the ones larger than sqrt(n) are associated with one smaller than sqrt(n), except for the case when sqrt(n) is a factor itself. Once you get above sqrt(n), you're not going to find any new factors.

Okay. If you want to increment by one, go for it.

cookiemonster

 

[abertram28]

i agreed with your sqrt(n) part.
what I am saying, is why go by odds?

why not reduce even further?

and then further...

and further...

further...

where is the limit?

the limit is having the list of primes, but the list of primes needs to be complete to n/2 if you start dividing by the number by 2 first, because this would reduce the time taken to complete the test. if the first prime number above sqrt(n) is contained within the known list, then no further testing of the number n/2 is required. i use n/2 as the limit for consideration for that reason. obviously that leads to the fastest calculation.

my method wasnt meant for the best or fastest computation. please understand that. it was meant for the most basic understanding. i wanted the person to be able to formulate their own program to derive the prime factors, and if they chose to start dividing n by (n/2) first, let them. they will get to the prime factors in less cycles than you in some cases.

also, if you were to start your iteration at the higher end, you might find that there are less cycles taken by starting at n/2 rather than sqrt(n). it really depends on your programming skill and programming language. I am not adverse to using sqrt(n) myself as the lower limit for the first half of the factors. you still have to test for primality of the factors above sqrt(n), right?

 

[cookiemonster]

No. If you start from the bottom and increment up, the smaller number in each factor pair will be a prime. You then restart the program on the second number in the pair.

i.e. n = 5*7*13 = 455

The program finds that 5 is the first factor and that 5*91 = 455. Set aside 5 and repeat the program for 91.

The program then finds that 7 is the first factor of 91 and that 7*13 = 91. Set aside 7 and repeat the program for 13.

The program then tests all integers up to \lfloor \sqrt{13} \rfloor = 3. None divide 13 evenly, so 13 is then the last prime. Set aside 13.

Now bring back all the numbers you set aside and you have the prime factorization of 455, i.e. 5*7*13.

Maybe we're not communicating with each other so well here, but I see no reason n/2 should ever be brought into this. Except if 2 is the first factor or something.

cookiemonster

 

[abertram28]

the reason i left n/2 as a limit and incremented by 1 are both similar. because math is learned by using it. i wanted the basic method to be understood and the details to be discovered by the person using/creating the said hypothetical program. you can just tell someone the answer, or you can give them the basic tools to find the answer. if you choose to give them the advanced set of tools, they won't understand how to make tools using the basic tools. when they find an advanced problem for which a certain advanced tool isn't in possesion, they won't understand how to use basic tools to create said advanced tool.

the reason i use n/2 as a limit is easy. there are more ways than one to make the program, and someone might just as easily start with n/2 and work downward if they so choose. we both know that starting smaller is better.

your whole point of iterating by a larger number is totally negated by the link you just provided, where as simple/faster means are used to test for many prime numbers, and the i need not be iterated for any number that isn't prime.
my point is only that the user who creates the program must have a crucial fundamental understanding of prime factorization and divisibility by those numbers in patterns. those patterns are great if you are doing it by hand, but if you are using a computer, that may be too complicated for some people to create in their first program.

and there are rules for divisibility by larger primes..
http://www.cut-the-knot.org/blue/FurtherDivisibility.shtml
http://mathforum.org/k12/mathtips/ward2.html
http://www.sonoma.edu/users/w/wilsonst/Courses/Math_300/fractions/divisibility/default.html

what do those and your link prove? that actually taking an iteration method approach is not the best, and therefore, improving it to the best program would negate its existence. that was my point in the beginning. A) we don't need these divisibility tests if we are using a computer, and B) having a list of primes is the fastest way.
based on that i use my n/2 method being faster than your

testing for divisibility by the prime factors less than sqrt(x) was your way.
my way might be to begin by dividing prime factors less than or equal to n/2 if n was a prime number other than 2, say p, and the number n was n=2*p, using the prime lookup method and my n/2 method you would find the first factor to be n/2, and prime factoring 2 is the fastest one. if you start at 2 and go to sqrt(n) youd first divide n/2 and take sqrt(n/2) and test for divisibility of all primes less than that number sqrt(n/2) youd have to test a bunch more numbers than i would. so you can't say that using sqrt(n) is the best way. it might be the best way for a specific program, but i didnt want to limit the poster as to his personal discoveries and insights into prime factorization. i just wanted a very quick and very dirty, but easy to follow method. and it was just that.

anyways, in the original context, having the limit of i going to n/2 vs sqrt(n) only applies as a benefit on the testing of the primality of the last factor, as the program would find a factor before it reached this number, and therefore, it would start the loop over. youd find that youd need a substantially large prime factor such that sqrt(n)-(n/2) was anything significant.

also, the basic algorithm i was describing at first was a specific test of primality based on no prior knowledge of prime numbers. it was meant to also be exhaustive so that the person could PROVE that the number was prime, not just find it was prime. for some people to see that its definitely prime, they would have had to divide it by every single number. not to say that its mathmatically necessary, but for some peoples logic it would be necessary. since we have computers to do it for us, that seemed to be the easiest way to convince the user that the numbers found were indeed prime.

 

[cookiemonster]

your whole point of iterating by a larger number is totally negated by the link you just provided,

As much as I like Robert, I kinda like my own life...

testing for divisibility by the prime factors less than sqrt(x) was your way.
my way might be to begin by dividing prime factors less than or equal to n/2 if n was a prime number other than 2, say p, and the number n was n=2*p, using the prime lookup method and my n/2 method you would find the first factor to be n/2, and prime factoring 2 is the fastest one. if you start at 2 and go to sqrt(n) youd first divide n/2 and take sqrt(n/2) and test for divisibility of all primes less than that number sqrt(n/2) youd have to test a bunch more numbers than i would. so you can't say that using sqrt(n) is the best way. it might be the best way for a specific program, but i didnt want to limit the poster as to his personal discoveries and insights into prime factorization. i just wanted a very quick and very dirty, but easy to follow method. and it was just that.

So you find 2 first and then test to see if p's a prime. Since it's a member of the list, we don't have to test anything. How's finding n/2 first faster?

anyways, in the original context, having the limit of i going to n/2 vs sqrt(n) only applies as a benefit on the testing of the primality of the last factor, as the program would find a factor before it reached this number, and therefore, it would start the loop over. youd find that youd need a substantially large prime factor such that sqrt(n)-(n/2) was anything significant.

\lfloor \sqrt{13} \rfloor = 3 2 numbers to test
\lfloor \frac{13}{2} \rfloor = 6 5 numbers to test

In the particular example I provided in my last post, using sqrt(n) vs. n/2 more than halves the number of factors to test.

Mathematically, we should only look for factors up to sqrt(n), but if you want to go to n/2, go for it.

also, the basic algorithm i was describing at first was a specific test of primality based on no prior knowledge of prime numbers. it was meant to also be exhaustive so that the person could PROVE that the number was prime, not just find it was prime. for some people to see that its definitely prime, they would have had to divide it by every single number. not to say that its mathmatically necessary, but for some peoples logic it would be necessary. since we have computers to do it for us, that seemed to be the easiest way to convince the user that the numbers found were indeed prime.

Then that should go to n-1, no?

Well, anyway, I have no intention of arguing any of these points further. Except for maybe the cookiemonster \neq robert Ihnot one.

cookiemonster

 

[robert Ihnot]

The problem 2343 is very easy. It may be that your teacher is not looking for a comprehensive prime factorization method, but only that you develope some facility at handling these kind of problems. I remember when I taught the subject, I had a problem on the test of factoring 121. I thought that very easy since, maybe, the students would know the squares up to say 12 or 20, but I was surprised to find that many did not know the answer on sight, nor the special rule for 11. Apparently our study of the matter had ended at 10, and no one had studied division by 11.

There are certain tests for small primes. With 2343 the sum of the digits is 12, which is divisible by 3. This leaves 781. But 7-8 +1 = 0, a test for division by 11. Thus factors are 3x11x71. Is 71 prime? Well, 9x9 = 81, so we only have to try primes less than 9. 2 and 3 are out, 5 is out since numbers divisible by 5 end in 5 or 0, and so 7 is the only possibility, but clearly it does not divide 71.

Thus problems like that are best attacked if you understand that 2,3,5, and 11 have simple tests, leaving only 7 to require actual division.

Now, there is a test for division by 7, if anyone wants to know. (I never learned that until graduate school): Drop the last digit of the number, double the dropped digit, and then subtract it off from the remaining number. iI what is left is divisible by 7, then the original number is divisible by 7. The rule can be repeated. In this case we had only to work with 71, which is not divisible since here we subtract 2 from 7, which is not divisible.

The rule for 13? I refer you to this website:

http://mathforum.org/k12/mathtips/division.tips.html

 

[Gokul43201]

Haven't really read through all the posts here, so this may be redundant...

1. Look for prime factors less than sqrt(n); or better still,

2. Look the Fermat's factorization algorithm.

For a whole host of factorization techniques, see : http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

 

[robert Ihnot]

The factorization brought up was 2343. The Fermat algorithm is intended for very large numbers, not those kind of things that could be solved in a minute or two. As I was suggesting in my own post, maybe what was at stake is just a little facility with numbers using pencil and paper, not an elaborate scheme, nor a computer program. Of course, when I taught calculators were not the norm in class.

If we need an elaborate scheme, why bother here? That kind of computer program is widely circulated. Many classes in computer programing go into that as an exercise.

 

[robert Ihnot]

The Fermat Method of Prime Factorization

In Fermat's day, there was no calculators. As for Gauss he enjoyed calculating, so that years ago a mathematician was expected to know how to calculate using pencil and paper.

Now for prime factorization starting with 2,3,5,7...the worst kind of cases would be those of two prime factors very close together. For example take

1021x1031 = 1,052,651.

We would have to try all the primes less than 1000 and still we would not have found the factorization. The method of Fermat relies on factorizing squares:

X^2-Y^2 =(x-y)(x+y)

So,since square roots can be found by hand, we could look at:

sqrt(1052651) = 1025.99, which is rather close to a possible factorization. So we look at:

X^2 = 1052652 +1, +4, +9, +16.+25 The last case gives: Sqrt(1052676)=1026 So it was only necessary to consider five cases. But, it is even simpler to just square 1026 = 1052667. (This also makes accuracy easier). Then subtracting off the original number of 1052651 leaves 25, the desired number for y^2.

Since 1021 is the 19th prime, we would have many more cases starting with small primes.

 

[JMDL1983]

Anyone able to help me?

I could really use a copy of your factoring program. Could you please email it to me at JMDL1983@HOTMAIL.COM? Also, anyone that has notes on how to go about creating a more complex factoring program. I need to break down a very large number actually, and having trouble doing so.

<-Challenge->
Status: Factored
Numbers Length: 576
Decimal Digits: 174
Digit Sum: 785
18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

if you start by dividing the number by two youll know what number the primes must lie below.

you could use brute force on the problem with a calculator and a list of known prime numbers less than 2344/2.

http://www.utm.edu/research/primes/lists/small/1000.txt this is a list of the first 1000 primes. you can use a calculator and start with the ones just less than 1172. if you find its divisible by 3 (add the digits to create a new number, then add the digits until you get a number you know is divisible by 3, like if you had 1234 youd add 1+2+3+4=10 which you know is not divisible by 3. if it is divisible by 3, then the result of dividing by 3 is also a factor. you can then factor the smaller number)


although kinda tedious, direct testing is the best way for smaller numbers.

start with 2,3,5. that will be easier. youll get to a point where youll have either a 2,3,5 or 7 and

2343 is divisible by 3. 2+3+4+3=12 1+2=3. ! so take 3 out.
2343/3 and 3 are factors. since three is prime, throw it in the prime factors.

so you have 781. you can cross check to see if 781 is prime with that link i gave. 781 isn't in that list, so begin by dividing by 7, since you can see its not a 2, 3, or 5. go up from there dividing with your calculator by prime numbers. if you get one, put the number in the prime factors list and continue.

i don't want to spoil the fun... but there are "factorizers" (programs to factorize or prime factor numbers) with the original or my personal favorite being the one that made the name. ill tell you it only finds 3, so from there, its up to you. the limit on the program i use is like 2.1 billion. after that, your on your own :p