<p>My TI-89 was able to take a number (approx = 1.66 septillion) and determine, in a second or two, that it was not prime.</p>
<p>Then, in 20 seconds or so, it was able to find the prime factorization:</p>
<p>1,659,216,587,925,851,659,122,111</p>
<p>= 3<em>3</em>3<em>3</em>477383*42909268672097657</p>
<p>How can it DO that? I don't know, I just thought it was interesting and amazing.</p>
<p>It would have to have an algorithm, I did one in CS that started at 2 and went up until it reached n/2, and if it had no factors, then it was prime. If it found a factor then it would say that it is not prime. To find the factorization, say it found 3 after checking 2, then it would take num/3 and check 2 then 3, all the way up to num/2. A calculator is 15mhz which is going to be a lot faster than a human, except that one guy on Ripleys.</p>
<p>To find the largest prime number, can't you just keep multiplying prime numbers together? By doing that a few times, wouldn't it give you a really, really large number? I don't see what the big deal with huge prime numbers is! Someone de-ignorize me!!</p>
<p>P.S.- valikor2, how did you get your calculator to do it? Is there some special program or does that function come standard in a ti-89?</p>
<p>KRabble...if you multiply a prime number by another than it now has 2 factors...those prime numbers. That is the reason 26 is not a prime number, even though 2 and 13 are both primes.</p>
<p>Oops! Thanks for the quick explanation. How did I forget?</p>
<p>multiplying prime numbers together will not give you a large prime number; if it's prime, it has to have no factors. But, you're right, in and of itself, there's nothing that great about really big prime numbers; what makes it amazing is that it can factor a number that big so quickly.</p>
<p>mattb--so there are algorithms for finding out if a number is prime? BESIDES trying to divide by 2, divide by 3, divide by 5, 7, etc? very cool.</p>
<p>KRabble -- factor() function works fine on integers as well as expressions</p>
<p>if you keep multiplying prime numbers together, how in hell would that give you a larger prime number? </p>
<p>the large number that you get HAS factors, THE ONES YOU JUST MULTIPLIED TO GET THE NUMBER! </p>
<p>i.e. 7 and 5 are prime but 35 (7 x 5) is not (1,35,7,5)</p>
<p>second of all, there is no such thing as a "largest prime number"... numbers increase infinitely, there is no cap on how large a number can get...</p>
<p>third of all, i'm craving some arby's... see ya</p>
<p>actually, you dont have to check factors till n/2, if you check till \sqrt{n} and n has no factors, then it is prime.</p>
<p>there are 3 easy tests to determine is n is not prime
Test 1: if GCD(a,n)
ot=1 for some integer a, then n is not prime. if this test fails, it tells you that GCD(a,n)=1, so you go on to test 2.
Test 2: this test is based on Fermat's theorem - if a^(n-1) is not congruent to 1 mod n, then n is composite; otherwise, this test failed and we go on to test 3 (the strongest test)
Test 3: if a^((n-1)/2) is not congruent to plus or minus 1 mod n, then n is composite; otherwise, this test failed too.
If all three tests fail, it is very likely that n is prime.</p>
<p>obviously, you dont need to use the 3 tests for easy numbers, but when you have numbers in the millions and billions digits, then they become quite useful - and yes, these big numbers are used in the various areas of the professional world.</p>
<p>I dont know if there really are, I think that they just use the rules for division of numbers, which would make them run faster. The isPrime() and factor() just call methods within the calculator that does some type of algorithm. To find out exactly what it is, you would have to learn assembly (Ti language) and then read through the code. That is the best way that I thought of when I had to do a lab. If you wonder how there are such good games for calc's, its because they are done in assembly and not on the ti, which for the 89, I cant even get how to do everything. Assembly is dangerous, you can seriously mess up your system. Thats why most schools dont want to teach it, high schools that is.</p>
<p>For those 3 tests, how do you determine the arbitrary number for a, can it be anything besides 1?</p>
<p>well, you look at the GCD. here is a def: GCD(a,b)=1 means integers a and b are relatively prime.
so for test 1, if GCD(a,n)
ot=1, then n is obviously not prime. and if GCd(a,n)=1, then you go on to the other tests.
so you can pick any a for test 2 and 3 as long as a is relatively prime to n. usually, you want to pick prime numbers less than \sqrt{n}</p>
<p>For easy #'s, it might seem useless to do test 1, but keep in mind that if the #'s are really big (i.e. million digits), you might just get lucky and pick an a such that GCD(a,n)
ot=1. if so, you dont have to check test 2 and 3 anymore:) this is why test 1 is aka the "lucky test"</p>
<p>You should look under number theory. Fermat's little theorem will give you a probable prime in a certain base (a). Then you can narrow the list... probable primes that are proven composite by checking for primality in a different base are called pseudo primes. There are corresponding strong probable primes, and strong pseudo primes.</p>
<p>Mathematicians consider primes to be the "atoms" of mathematics because they cannot be factored. Any progress in the understanding of these numbers is considered to be quite important.</p>
<p>3<em>3</em>3<em>3</em>477383*42909268672097657, is not prime</p>
<p>please, try this:</p>
<p><a href=“http://www.csgnetwork.com/mthprimenumber.html[/url]”>http://www.csgnetwork.com/mthprimenumber.html</a></p>
<p>It found the factors quickly because they are so low (3s) - easy to screen for by adding the digits, and easy to factor out. The large prime factor that remained is much smaller than the original number. </p>
<p>It is generally very difficult to compute the prime factors of a very large number of the factors are also very large. This is the basis of common cryptography algorithms.</p>