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?
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 has a prime factor calculator.
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.
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.
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.
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.
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.
[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]
If you want a real prime number calculator, try this one: 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).
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.
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.
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.
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.
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.
