Well lots of posts abt primality testing. But what my frnd Venks wants is not a linear algo, not something like, run down from that number till u get a prime and use an efficient method to do ur primality testing. what i presume he wants is a way of jumping over numbers without missing any primes inbetween. of course i dont have an asnwer, not even sure if one exists, but i guess this is what we shd be discussing.
-Vijay
On 11/30/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED]> wrote:
Well sorry...
Kindly excuse my ignorance...
I believe nothing is known about the class to which the factorization
problem belongs to...
As with the AKS algorithm... yes! "primes is in p" but many more primality
testing algorithms are also known to run in P type provided the extended
riemann hypothesis is assumed...
Nice to see some primo discussions on an algo group :-)
Keep posting.
sudarshan
----- Original Message -----
From: "Dhyanesh" <[EMAIL PROTECTED]>
To: <algogeeks@googlegroups.com >
Sent: Wednesday, November 30, 2005 8:41 PM
Subject: [algogeeks] Re: how to find Previous Prime number?
Hi
It is not an NP complete problem, it has been one of the open problems
for quite some time. And by the way determining whether a number is
prime or not is surely not NP, it is in P. This is not an approximate
algorithm or anything. Here is the link to the paper:
http://www.cse.iitk.ac.in/users/manindra/primality_original.pdf
Also read the last paragraph on this link:
http://www.guajara.com/wiki/en/wikipedia/c/co/co_np.html
-Dhyanesh
On 11/30/05, SUDARSHAN IYENGAR < [EMAIL PROTECTED]> wrote:
>
> factoring is an np complete problem. No change of having a simple
algorithm
> for it.
>
> -sudarshan
>
> ----- Original Message -----
> From: "Dhyanesh" <[EMAIL PROTECTED]>
> To: < algogeeks@googlegroups.com>
> Sent: Wednesday, November 30, 2005 7:47 AM
> Subject: [algogeeks] Re: how to find Previous Prime number?
>
>
>
> I believe there is an N^12 algorithm for integer factorization ... so
> it isnt all that hard i think ...
>
> On 11/29/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED]> wrote:
> >
> > primality testing is a very very very tough topic to discuss...
> >
> >
> > There is no single algorithm for primality testing... and all that is
> known
> > so far is nothing but intelligent brute forcing...
> >
> > try peeping through http://primepages.org more like a bible for prime
> number
> > lovers.
> >
> > -Sudarshan
> >
> >
> >
> > The hardest thing to understand is why we can
> > understand anything at all
> > - Einstein
> > ----- Original Message -----
> > From: "Venkatesh Dayalan" <[EMAIL PROTECTED]>
> > To: < algogeeks@googlegroups.com>
> > Sent: Tuesday, November 29, 2005 7:53 PM
> > Subject: [algogeeks] Re: how to find Previous Prime number?
> >
> >
> > thanks for the info....
> > but i am looking into the logic of finding the previous prime number...
> >
> >
> > On 11/29/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED] > wrote:
> > >
> > >
> > > hey well... you must have a look at this package "pari gp"
> > >
> > > try googling and you can download this package, its very small and is
> the
> > > best of its kind available till date... You can also get the code for
> the
> > > same...
> > >
> > > -Sudarshan
> > >
> > >
> > > ----- Original Message -----
> > > From: <[EMAIL PROTECTED]>
> > > To: "Algorithm Geeks" < algogeeks@googlegroups.com>
> > > Sent: Tuesday, November 29, 2005 7:45 PM
> > > Subject: [algogeeks] how to find Previous Prime number?
> > >
> > >
> > > >
> > > > Hi everbody
> > > > Given a number which can be as long as 10000 digits, is there a
method
> > > > to find the previous prime number to it?
> > > >
> > > > ~venkatesh
> > > >
> > >
> > >
> >
> >
> > --
> > "There is no Spoon"
> >
> > "asato ma sad gamaya - From delusion lead me to truth
> > tamaso ma jyotir gamaya - From darkness lead me to light
> > mrtyor mamrtam gamaya" - From death lead me to immortality
> >
> >
>
>
