- #1

saadsarfraz

- 86

- 1

## Homework Statement

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.

## Homework Equations

see above

## 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 don't 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: