Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   Calculus & Beyond Homework (http://www.physicsforums.com/forumdisplay.php?f=156)
-   -   Algorithm for prime factorization (http://www.physicsforums.com/showthread.php?t=287731)

saadsarfraz Jan26-09 08:55 PM

Algorithm for prime factorization
 
1. The problem statement, all variables and given/known data

One algorithm for finding the prime factorization of a number n is the following: Starting with d = 2, and continuing until n[tex]\geq[/tex]d, try to divide n by d. If n/d, then record d as a (prime) factor and replace n by n/d; otherwise replace d by d + 1.

a) When d is recorded, how do we know that d is prime?
b) Suppose n = ab. Show that a[tex]^{2}[/tex][tex]\leq[/tex]n or b[tex]^{2}[/tex][tex]\leq[/tex]n
c)Use this fact to improve the algorithm.

2. Relevant equations

see above

3. The attempt at a solution

for part a, since we are dividing by a prime number that is how we know that d is prime. I dont know how to do part b but, i think it might have something to do with a/p or b/p, where p is the prime number.

Dick Jan26-09 10:00 PM

Re: Algorithm for prime factorization
 
I think you mean replace n by n/d. But if you are starting with d=2 and dividing n by d, then incrementing d and trying again, for the FIRST value of d that divides n, d MUST be prime. Can you say why?

saadsarfraz Jan27-09 03:48 AM

Re: Algorithm for prime factorization
 
i corrected the error. I'm still unsure about this but the fundamental theorem of arithmetic states that every natural number greater than 1 can be written as a unique product of prime numbers, since d is the first number we are dividing it by, therefore it must be prime.

Dick Jan27-09 09:11 AM

Re: Algorithm for prime factorization
 
Quote:

Quote by saadsarfraz (Post 2051312)
i corrected the error. I'm still unsure about this but the fundamental theorem of arithmetic states that every natural number greater than 1 can be written as a unique product of prime numbers, since d is the first number we are dividing it by, therefore it must be prime.

That's not super clear. But if d isn't prime then it's divisible by another number. Say e. And e<d. What does that mean in terms of the algorithm?

symbolipoint Jan27-09 12:54 PM

Re: Algorithm for prime factorization
 
One way to handle the factorization is to divide only by prime numbers. I made a factorization program a few years ago. I used the Sieve of Eratosthenes process to find a list of primes, and then I performed a succession of divisions up to a certain value (square root of something,... forgot the exact reason for this).

saadsarfraz Jan27-09 08:19 PM

Re: Algorithm for prime factorization
 
the only number less than d would be 1 then but the fundamental theorem of arithmetic says that it should be greater than 1, so the next prime number is 2.

Dick Jan27-09 10:30 PM

Re: Algorithm for prime factorization
 
Quote:

Quote by saadsarfraz (Post 2052270)
the only number less than d would be 1 then but the fundamental theorem of arithmetic says that it should be greater than 1, so the next prime number is 2.

You still don't get it. If you start from 2 and divide n by successive integers, the first d that divides n MUST be prime, otherwise you would have divided n with another integer before you hit d. Right? Right? Right? Don't just quote abstractions, think about it.

saadsarfraz Jan27-09 10:51 PM

Re: Algorithm for prime factorization
 
so if i take n=32 for example then 32/4=8, and 8/4=2, 2/2=1. got it. btw i'm also having some trouble doing part c).

Dick Jan27-09 10:57 PM

Re: Algorithm for prime factorization
 
It's what symbolpoint said. If you don't find a divisor before you hit sqrt(n), you may as well quit. You aren't going to find one. Why?

saadsarfraz Jan27-09 11:28 PM

Re: Algorithm for prime factorization
 
is it because the n/d would no longer be divisible by d, if a<=sqrt(n) or b<=sqrt(n) then can it be that ab<n??? I donr really know how to answer this.

Dick Jan28-09 08:54 AM

Re: Algorithm for prime factorization
 
If n=a*b, that's a factorization of n. If both factors were greater than sqrt(n) then a*b>n. That can't be since a*b=n. So at least one of factors a or b must be less than sqrt(n).

saadsarfraz Jan28-09 11:26 AM

Re: Algorithm for prime factorization
 
so if the number which is greater than square root of n is not divisible by d then, there are no prime factors for that n?

Dick Jan28-09 02:16 PM

Re: Algorithm for prime factorization
 
No. If n has divisors, then at least one of them must be less than or equal to sqrt(n).


All times are GMT -5. The time now is 12:55 AM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums