(adsbygoogle = window.adsbygoogle || []).push({}); 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.

**Physics Forums - The Fusion of Science and Community**

# Algorithm for prime factorization

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Algorithm for prime factorization

Loading...

**Physics Forums - The Fusion of Science and Community**