[news] Student finds largest known prime number

[Handruin]

DETROIT, Michigan (AP) -- More than 200,000 computers spent years looking for the largest known prime number. It turned up on Michigan State University graduate student Michael Shafer's off-the-shelf PC.

"It was just a matter of time," Shafer said.

The number is 6,320,430 digits long and would need 1,400 to 1,500 pages to write out. It is more than 2 million digits larger than the previous largest known prime number.

Link Source

 

[Howell]

I was wondering where I left that. How it got into his computer, I'll never know.

 

[blakerwry]

man, that's an interesting data class they used... the ability to hold numbers that large... I wonder if they used a string and converted it to a number or if they used a data type that is natively a number...

By my dumb math, the minimum size of this data type would have to be atleast 2,661,234 bytes. ...While most whole number variables are limited to just a few bytes... integers, for example, are usually limited to 4 bytes (2,147,483,647).. long integers: 8 bytes (9,223,372,036,854,775,807)

 

[CougTek]

Why people are so interested in prime numbers? What's the damn use for them? I mean : "Wow! Number xyz can only be divided by 1 and itself, it brought joy to my heart and changed my life!"

An exercice in futility.

 

[Mercutio]

Primes are used extensively in Cryptography, Coug. Very useful application.

Calculating pi is pretty much useless on the other hand.

 

[blakerwry]

i like pi

 

[blakerwry]

aparently I was pretty close.. the number he found was 2,624,502 bytes in size.

 

[blakerwry]

and btw, that number freezes my calculator when I try to display it ;-)

boy I'm a geek.

 

[sechs]

There's a very straightforward algorithm for finding one prime number when you know another. It's simply time consuming to run it on a computer when the numbers are so large.

 

[blakerwry]

yup

for (x=3.0; x<infinite;x++)
{
  possiblePrime = 2^x-1
  for(y=possiblePrime-1; y>1; y--)
  {
    if (possiblePrime/y == round(possiblePrime/y)) //very slow way to check if the possible Prime is divisable
    {
      not-a-prime = true;
    }
  }
  if(!not-a-prime)
  {
    cout << "Prime: " + possiblePrime + "\n";
  }
   not-a-prime = false;
}

I think that would work..... been along time since I messed with C++. The problem is getting the datatype large enough to hold those large numbers while still being fast. (and also a faster error detection routine then the simple one I divised here.)

 

[Tannin]

Primes are used extensively in Cryptography.

For some reason, possibly having to do with not drinking regularly enough, I have this picture of a panic-stricken secret agent somewhere in the wilds of Siberia. He urgently needs to send the message: "the missing nuke is buried three miles west of the tractor factory" before the KGB tracker dogs catch up with him and rip his legs off.

Meanwhile, all he has to do is type in his 140-page secret encription key and press "send".

 

[sechs]

blakerwry, that's just a really crappy way to test if all numbers are prime.

There are a couple P-time algorithms to test for primality; although I'd expect them to use Marsene numbers and the Lucas-Lehmer test.

 

[blakerwry]

yeah, I realize that. That's what you get when you write a program in 2 minutes and you dont want to have to error check it for every possible value.

I imagine that you could try to devide the possible prime number by (2^a)-1 where the value of a is decreased everytime. It would be exponentially faster, but I didnt want to see if it worked in all cases.

 

[sechs]

yeah, I realize that. That's what you get when you write a program in 2 minutes and you dont want to have to error check it for every possible value.

I think that would be called "running the program." You wouldn't have big enough variables anyway.

 

[blakerwry]

unfortunately I dont have a c++ compiler on my system to run this program... and you're right, I dont have big enough variables... I wouldn't even know where to start to get variables as big as those used by the program featured in the news article...

I know java has a big integer class, but I doubt it's that big... I could create my own data type using something like linked lists(pretty much infinite size), but it would be slow and involve a bunch of coding...

I'm not familiar with how to create linked lists in c++ so I'd have to transfer this to the slower JAVA language... or learn more about pointers in C++.