# So much for running Prime95

#### Krusty

##### Insane Overclocking Clown
It looks like we no longer need to use a brute force method to find out if a number is prime. Manindra Agrawal Figured out how to do it in 13 lines of code. His "Primes in P" paper shows how do to it. You will need a postscript viewer like ghostview to see it though. Acrobat won't do it.

#### RangerJoe

##### All that is Man!
where can i get this viewer? id like to see it

#### Crash893

##### "The man in black fled across the desert,
yea me too

( i posted this up on the prime 95 froum ill let you know what they think about it)

OP

#### Krusty

##### Insane Overclocking Clown

It's a bit of an odd program. I downloaded the postscript file and clicked the 'open with' option and chose ghostview to get the program to open the file. Hit enter to scroll to the next page.

#### JigPu

##### Inactive Pokémon Moderator
6 meg too big for me... Can you sum it up? Mabey I'll come up with a way to optimize my prime program a little more

EDIT: The Prime Pages has a little section on it... Now to figure it out

EDIT #2: OK, I think I get the general concept, but not the implementation. There are variables mentioned in the proof of the algorithm that don't appear in the formua... Perhaps I should Google around for info... Unless somebody feels up to explaining it

EDIT #3: Yea!! I've found a page that explains the algorithm!! Seems I was kinda right on how it works, and learned a few new things in the process. Now, to turn that pseudo-code into a program!!

JigPu

Last edited:
OP

#### Krusty

##### Insane Overclocking Clown
I haven't taken the time to read through it myself (have a computer logic and design midterm tomorrow), so would someone mind telling me a couple of things if you find it?

1. What is the O-notation of the currently used prime number finding programs?

2. What is the O-notation of the one this guy found?

I'll do some more looking at it in a couple days, so it's no biggie if nobody knows.

EDIT: Jig Pu, can you give us a little linkage to the non-post script version you found?

#### RangerJoe

##### All that is Man!
i cant figure out how to open the file...i unzipped ghostview..and i downloaded the primality.ps file, but have no clue how to use it

OP

#### Krusty

##### Insane Overclocking Clown
RangerJoe said:
i cant figure out how to open the file...i unzipped ghostview..and i downloaded the primality.ps file, but have no clue how to use it

right click on the primality.ps file, select open with. select choose program. click other. it will be somewhere like c:\program files\ghostview\gs7.04\bin. choose gswin32c. Then the primality.ps program will be opened with ghostview.

Use the scroll bar to go up and down in the page. Use the enter key to go to the next page.

#### RangerJoe

##### All that is Man!
woah, crazy, when i opened the file, adobe distiller changed it into a .pdf file, and it all works, thats kinda handy

OP

#### Krusty

##### Insane Overclocking Clown
zip that baby up and upload it here for us then. I'd like to have it in pdf format.

ditto

dotti

#### Crash893

##### "The man in black fled across the desert,

AKS - A polynomial-time algorithm for testing primality.

The main significance of the AKS algorithm is that it is the first *provably*
polynomial-time scheme for proving primality (or not) of any desired number.
That doesn't mean it's necessarily faster in practice than schemes such
as ECPP, which are polynomial time for nearly all inputs (and many such schemes
are in fact polynomial time for ALL inputs if the Extended Riemann Hypothesis
is true - it probably is, but AKS doesn't need it to be). And for numbers of
special form (e.g. Mersennes, Fermats, Proths, etc.) there are well-known
deterministic primality tests that are not only polynomial time, but also
much faster than AKS, ECPP, etc. So don't expect to replace Prime95 with
anything else just yet.

Cheers,
-Ernst

if that didn't make any sense to you, just think that there are very fast ways that 'special' numbers like mersennes can be checked. The downside is that you can ONLY find mersenne numbers (or other similar numbers) with this special algorithm, but you can still find larger numbers faster.

This new way is an algorithm that'll find if ANY number is prime, but while it's faster than checking all the primes less than the Square Root of the number in question, it's not nearly as fast as P95 at checking mersenne numbers in the special form (2^k)-1.

#### nihili

##### Inactive Doc Logic Philosophical Mod
Nice summary Crash, Thanks.

#### Crash893

##### "The man in black fled across the desert,
thanks but its not mine its the reply from the prime guys over on there forum

#### RangerJoe

##### All that is Man!
crap..i cant get it any smaller than 148kb...thats zipped, how can i get it smaller?

#### Crash893

##### "The man in black fled across the desert,
span it to two diffent files

OP

#### Krusty

##### Insane Overclocking Clown
crash893 said:
span it to two diffent files

winRAR should do the trick there.

Replies
4
Views
96
Replies
3
Views
425
Replies
6
Views
272
Replies
30
Views
668
Replies
14
Views
368