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