Algorithm for prime factorization

  1. Jan 26, 2009 #1
    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.
     
    Last edited: Jan 27, 2009
  2. jcsd
  3. Jan 26, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Jan 27, 2009 #3
    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.
     
  5. Jan 27, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. Jan 27, 2009 #5

    symbolipoint

    User Avatar
    Homework Helper
    Education Advisor
    Gold Member

    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).
     
  7. Jan 27, 2009 #6
    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.
     
  8. Jan 27, 2009 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  9. Jan 27, 2009 #8
    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).
     
  10. Jan 27, 2009 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  11. Jan 27, 2009 #10
    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.
     
  12. Jan 28, 2009 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  13. Jan 28, 2009 #12
    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?
     
  14. Jan 28, 2009 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No. If n has divisors, then at least one of them must be less than or equal to sqrt(n).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Algorithm for prime factorization
Loading...