# Algorithm for prime factorization

In summary, the conversation discusses an algorithm for finding the prime factorization of a number, where the first number to divide n is considered prime. The conversation also mentions the fundamental theorem of arithmetic and discusses the importance of considering the square root of n when finding prime factors. The final part of the conversation focuses on how this information can be used to improve the algorithm.

## Homework Statement

One algorithm for finding the prime factorization of a number n is the following: Starting with d = 2, and continuing until n$$\geq$$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$$^{2}$$$$\leq$$n or b$$^{2}$$$$\leq$$n
c)Use this fact to improve the algorithm.

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

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.

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?

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

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.

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.

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

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?

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.

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

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?

No. If n has divisors, then at least one of them must be less than or equal to sqrt(n).

## 1. What is an algorithm for prime factorization?

An algorithm for prime factorization is a method or set of steps used to find the prime factors of a given number. Prime factors are the prime numbers that can be multiplied together to get the original number.

## 2. How does the algorithm for prime factorization work?

The algorithm for prime factorization typically involves dividing the given number by the smallest prime number possible and then repeating the process with the resulting quotient until the quotient is equal to 1. The prime numbers used in the division are the prime factors of the given number.

## 3. Why is prime factorization important?

Prime factorization is important in various fields of mathematics, such as cryptography and number theory. It is also used in data encryption and compression, as well as in finding the greatest common divisor and least common multiple of two numbers. Additionally, it helps in simplifying fractions and solving certain types of equations.

## 4. Is there more than one algorithm for prime factorization?

Yes, there are multiple algorithms for prime factorization, each with its own advantages and disadvantages. Some common algorithms include trial division, Pollard's rho algorithm, and the quadratic sieve algorithm. The best algorithm to use may depend on the size of the number being factored and the available computing resources.

## 5. Can prime factorization be used for large numbers?

Yes, prime factorization can be used for large numbers, but it becomes more computationally intensive as the numbers get larger. For extremely large numbers, specialized algorithms and advanced computing techniques may be necessary. However, for everyday numbers, the algorithm for prime factorization can be easily implemented and used to find the prime factors.

Replies
4
Views
1K
Replies
2
Views
2K
Replies
13
Views
3K
Replies
2
Views
3K
Replies
3
Views
962
Replies
5
Views
1K
Replies
9
Views
2K
Replies
15
Views
3K
Replies
6
Views
1K
Replies
3
Views
936