• Welcome to Overclockers Forums! Join us to reply in threads, receive reduced ads, and to customize your site experience!

So much for running Prime95

Overclockers is supported by our readers. When you click a link to make a purchase, we may earn a commission. Learn More.

Krusty

Insane Overclocking Clown
Joined
Sep 17, 2001
Location
Orange County
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.
 

Crash893

"The man in black fled across the desert,
Joined
Mar 13, 2001
yea me too

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

Krusty

Insane Overclocking Clown
Joined
Sep 17, 2001
Location
Orange County
ghostview can be downloaded here.

Scroll down to the windows 9x/2k/xp section to download it.

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
Joined
Jun 20, 2001
Location
Vancouver, WA
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 :D

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

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 :D

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!! :D

JigPu
 
Last edited:
OP
Krusty

Krusty

Insane Overclocking Clown
Joined
Sep 17, 2001
Location
Orange County
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?
 
OP
Krusty

Krusty

Insane Overclocking Clown
Joined
Sep 17, 2001
Location
Orange County
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.
 
OP
Krusty

Krusty

Insane Overclocking Clown
Joined
Sep 17, 2001
Location
Orange County
zip that baby up and upload it here for us then. I'd like to have it in pdf format.
 

Crash893

"The man in black fled across the desert,
Joined
Mar 13, 2001
The short answer is: no.

There is some discussion and links in the Math thread titled

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.
 

Crash893

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