Thread: Finding factors of a number

1. Finding factors of a number

Hi,

I hope someone can help.

I am trying to developed an algorithm which based on a given input, call it x, determines whether x is prime.

One way to do this is to check all the numbers (starting at 2) up to x/2 is divisible by x. If there is such a number, then x is not prime. I understand this strategy completely.

However, another way to to check all numbers (starting at 2) up to the square root of x. Can someone please explain to be why this works?

2. Re: Finding factors of a number

For instance, we have the pairs (1,12), (2,6), and so on as factors of 12 as shown in the first table.

Notice that the 4th, 5th, and 6th pairs are just reverses of the first three pairs. In effect, we just need to include the first three pairs to be sure that we have all the factors. This is also the similar in the second example. We only need to test the divisibility up to 4 and we have already all the factors. No need to test divisibility by 5 up to 16. (To verify further, try factors of other composite numbers.)

You have probably noticed that there is some sort of middle number in both tables denoted by the red-colored text. After the middle number, the pairs are mere repetitions of the other pairs.

In the first table, the middle number is 3, while in the second table, the middle number is 4. Four is the square root of 16, and testing more perfect squares (the reader is encouraged to do so) will confirm the observation.

From above, we can conjecture that every composite number has a factor less than or equal to its square root. Proving this is the same as proving that a number that has no divisor greater than 1 and less than its square root is prime.

The Formal Proof

Conjecture: Every composite number has a proper factor less than or equal to its square root.

Proof: We use proof by contradiction. Suppose n is composite. Then, we can write n = ab, where a and b are both between 1 and n. If both $a > \sqrt{n}$ and $b> \sqrt{n}$, then$(a)(b) > (\sqrt{n})(\sqrt{n})$ which means that $ab > n$. This contradicts our assumption that $ab = n$. Hence, at least one of $a, b$ is less than or equal to $\sqrt{n}$. That is, if $n$ is composite, , then n has a prime factor $p \le \sqrt{n}$.

3. Re: Finding factors of a number Originally Posted by otownsend I am trying to developed an algorithm which based on a given input, call it x, determines whether x is prime.
One way to do this is to check all the numbers (starting at 2) up to x/2 is divisible by x. If there is such a number, then x is not prime. I understand this strategy completely.
However, another way to to check all numbers (starting at 2) up to the square root of x. Can someone please explain to be why this works?

If $n=4276800$ then $n$ can be factored as $2^6\cdot 3^5\cdot 5^2\cdot 11$, SEE HERE. On that webpage we are told that $n$ has $252$ divisors.

Here is more interesting question. Suppose $\{p,q,r,s,t\}$ is a set of five prime numbers, and $N=p^4\cdot q^3\cdot r^7\cdot s^2\cdot t^6$.

How many factors does the number $N$ have?

4. Re: Finding factors of a number

Hey, thanks for your reply mak21. The formal proof you provided is clear to be. However, you seem to be referring to a table that isn't actually available in the post itself ... are you missing an attachment or link? Please let me know.

Search Tags

algorithm, prime, prime divisor 