# Common Denominators
**URL:** https://boards.straightdope.com/t/common-denominators/184287
**Category:** Factual Questions
**Created:** [June 25, 2003, 1:47pm UTC](https://boards.straightdope.com/t/common-denominators/184287 "2003-06-25T13:47:16Z")
**Posts on this page:** 18
**Page:** 1
### Author:  [@yoyo3500](https://boards.straightdope.com/u/yoyo3500)
#### Post date: [June 25, 2003, 1:47pm UTC](https://boards.straightdope.com/t/common-denominators/184287/1 "2003-06-25T13:47:16Z")
I just got my number for a race and the number is 15457. I was curious if it was a prime number, so I checked a list of the first 10,000 prime numbers and found out that is not. (However, 15451 and 15461 are!) So then I was wondering what the denominators of 15457 are, and then I wondered how I would go about doing figuring this out.
Aside from the process of elimination, is there a mathmatical shortcut to finding denomninators? Also, is there a website that runs a quick check for denonimators?
This may one day help me to take over the world.
---
### Author:  [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)
#### Post date: [June 25, 2003, 2:05pm UTC](https://boards.straightdope.com/t/common-denominators/184287/2 "2003-06-25T14:05:29Z")
The prime factors of 15457 are 13 \* 29 \* 41. From these you can determine all the factors. For example, (13 \* 29) \* 41 = 377 \* 41 = 15457. [This page](http://www.math-it.de/Mathematik/Zahlentheorie/Zahl/ZahlApplet.html) has a prime factor calculator.
---
### Author:  [@yoyo3500](https://boards.straightdope.com/u/yoyo3500)
#### Post date: [June 25, 2003, 2:10pm UTC](https://boards.straightdope.com/t/common-denominators/184287/3 "2003-06-25T14:10:04Z")
Thanks! This is so cool (in a mathmatical sorta’ way)!😃
---
### Author:  [@The\_Weak\_Force](https://boards.straightdope.com/u/The_Weak_Force)
#### Post date: [June 25, 2003, 5:44pm UTC](https://boards.straightdope.com/t/common-denominators/184287/4 "2003-06-25T17:44:39Z")
> [@](#):
>
> Aside from the process of elimination, is there a mathmatical shortcut to finding denomninators?
> [@](#):
>
> This may one day help me to take over the world.
I know you meant this jokingly, but if you actually found a good shortcut for finding factors of big numbers, and you didn’t tell anyone about it, you could probably take over the world with just a little more effort. That’s because most modern cryptography (“secure” communications, for example) relies heavily on the belief that factoring large numbers is very, very, difficult, even though multiplying the factors to produce a big number is easy. In today’s world, a fast factoring algorithm would give you immense power, if you could keep the secret.
---
### Author:  [@frixxxx](https://boards.straightdope.com/u/frixxxx)
#### Post date: [June 25, 2003, 5:49pm UTC](https://boards.straightdope.com/t/common-denominators/184287/5 "2003-06-25T17:49:33Z")
Well as far as prime numbers go, that’s basically the concept for alot of computer security algorithms. If it were easy, I’d hate to figure out what we would have to use next.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [June 25, 2003, 7:00pm UTC](https://boards.straightdope.com/t/common-denominators/184287/6 "2003-06-25T19:00:43Z")
There are other options–problems that are known to be _very_ hard to solve. Deciding whether two regular expressions with exponentiation is one of them (for you geeks out there, it’s known to lie outside of NP).
The best (publicly) known factoring algorithm is to try every prime number less than half the input. You’d have to refine that a bit to get the exact factorization, but it’s not so hard.
---
### Author:  [@yoyo3500](https://boards.straightdope.com/u/yoyo3500)
#### Post date: [June 25, 2003, 8:26pm UTC](https://boards.straightdope.com/t/common-denominators/184287/7 "2003-06-25T20:26:40Z")
Hmmm. Then maybe if I try realy hard and learn all the primes, then I just **might** be able to take over the world…
😉
---
### Author:  [@frixxxx](https://boards.straightdope.com/u/frixxxx)
#### Post date: [June 25, 2003, 8:43pm UTC](https://boards.straightdope.com/t/common-denominators/184287/8 "2003-06-25T20:43:45Z")
> [@](#):
>
> \*Originally posted by yoyo3500 \*
> \*\*Hmmm. Then maybe if I try realy hard and learn all the primes, then I just **might** be able to take over the world…
>
> 😉 \*\*
OK Mr Nash, (Dangerous Minds) :dubious: But seriously let me add a twist to the OP, is zero “0” a prime number?
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [June 25, 2003, 8:46pm UTC](https://boards.straightdope.com/t/common-denominators/184287/9 "2003-06-25T20:46:58Z")
No, 1 and 0 are neither prime nor composite. 1 is a unit, because it has a reciprocal. 0 is a zero divisor, because there is a number a such that 0a = 0.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [June 25, 2003, 8:52pm UTC](https://boards.straightdope.com/t/common-denominators/184287/10 "2003-06-25T20:52:43Z")
No, 1 and 0 are neither prime nor composite. 1 is a unit, because it has a reciprocal. 0 is a zero divisor, because there is a number a such that 0a = 0.
---
### Author:  [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)
#### Post date: [June 25, 2003, 9:07pm UTC](https://boards.straightdope.com/t/common-denominators/184287/11 "2003-06-25T21:07:43Z")
[nitpick]You are not asking about common denominators. A denominator is the bottom integer in a rational expressed as p/q. If you wish to add two rational numbers, you first find the least common denominator or the least common multiple of the denominators. For example 1/6 + 1/4, you find the least common multiple of 6 and 4, which would be 12. 1/6 + 1/4 = 2/12 + 3/12 = 5/12.
You are seeking a short cut to prime factorization.[/nitpick]
---
### Author:  [@frixxxx](https://boards.straightdope.com/u/frixxxx)
#### Post date: [June 25, 2003, 9:47pm UTC](https://boards.straightdope.com/t/common-denominators/184287/12 "2003-06-25T21:47:03Z")
> [@](#):
>
> \*Originally posted by DrMatrix \*
> **[nitpick]You are not asking about common denominators.**
Sorry Doc, we got sidetracked!
---
### Author:  [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)
#### Post date: [June 25, 2003, 10:29pm UTC](https://boards.straightdope.com/t/common-denominators/184287/13 "2003-06-25T22:29:13Z")
> [@](#):
>
> \*Originally posted by ultrafilter \*
> \*\*There are other options–problems that are known to be _very_ hard to solve. Deciding whether two regular expressions with exponentiation is one of them (for you geeks out there, it’s known to lie outside of NP).
>
> The best (publicly) known factoring algorithm is to try every prime number less than half the input. You’d have to refine that a bit to get the exact factorization, but it’s not so hard. \*\*
I thought it was every prime number less than the SQUARE ROOT of input.
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [June 26, 2003, 12:40am UTC](https://boards.straightdope.com/t/common-denominators/184287/14 "2003-06-26T00:40:37Z")
If you want a real prime number calculator, try this one:
[http://www.alpertron.com.ar/ECM.HTM](http://www.alpertron.com.ar/ECM.HTM)
The site cited above talks about several seconds for factoring ten digit numbers. This one claims to do up to 1000 digit numbers and I have tested it on numbers in excess of 100 digits, which are usually instantaneous. The home site has other functions, including expressing giant numbers as sums of 4 squares (or fewer; every positive number is the sum of four or fewer squares).
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [June 26, 2003, 1:06am UTC](https://boards.straightdope.com/t/common-denominators/184287/15 "2003-06-26T01:06:40Z")
> [@](#):
>
> \*Originally posted by Enola Straight \*
> \*\*I thought it was every prime number less than the SQUARE ROOT of input. \*\*
That’s for primality checking. 10 = 2\*5, and 5 \> sqrt(10). You might be able to use the square root limit to get a slightly faster algorithm, but it’s still gonna be slow.
---
### Author:  [@The\_Weak\_Force](https://boards.straightdope.com/u/The_Weak_Force)
#### Post date: [June 26, 2003, 4:25am UTC](https://boards.straightdope.com/t/common-denominators/184287/16 "2003-06-26T04:25:16Z")
> [@](#):
>
> If you want a real prime number calculator, try this one:
I asked it to factor
43859 299303 000002 218383 859599 333000 203477 473329 929493 950035 035035 028888 599324 145258 321244 245453 219892 243243. It’s certainly taking its sweet time. 40 minutes and still chomping 😃
---
### Author:  [@The\_Weak\_Force](https://boards.straightdope.com/u/The_Weak_Force)
#### Post date: [June 26, 2003, 1:58pm UTC](https://boards.straightdope.com/t/common-denominators/184287/17 "2003-06-26T13:58:56Z")
Hmmm…10 hours, and still going. I think it’s time to call it quits. ☹
It got as far as 6514 271221 x 256775 555903 x 26 220572 785755 287534 635340 372130 205916 795403 097102 000658
687132 682152 917036 626065 331361.
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [June 26, 2003, 8:36pm UTC](https://boards.straightdope.com/t/common-denominators/184287/18 "2003-06-26T20:36:38Z")
1. Finding an efficient algorithm for factoring will break only a few codes. E.g., PGP. Other systems, such as DES, RSA4 or quadratic residue would be unaffected. Global domination is unlikely to occur.
2. There are _much_ faster algorithms for factoring than the old seive methods. No one doing serious factoring uses seives. Len Adelman has held, or knows he who holds, the record for fastest factoring algorithm for a couple decades now. A good name to Google on.
3. You do only have to go up to square roots, once you find that 2 is a factor of 10, you factor it out and get 5. If you have all factors less than the square root, you can trivially determine the larger factors as well. But again, no one uses this in serious computation.