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

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.

Re: Algorithm for prime factorization
Quote:

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

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.

Re: Algorithm for prime factorization
Quote:

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

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?

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.

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

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?

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 09:13 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums