Prime Number !!!

[ajay.ajaysharma]

Hello,

I need the EFFICIENT algorithm for finding whether given number is
prime
or not.

Regards,
Ajay

 

[Rafal 'Raf256' Maj]

(e-mail address removed)

I need the EFFICIENT algorithm for finding whether given number is
prime
or not.

GPM math library have meany good functions in that subject.

 

[SM Ryan]

(e-mail address removed) wrote:
# Hello,
#
# I need the EFFICIENT algorithm for finding whether given number is
# prime
# or not.

NSA needs one too. Many cipher systems depend on the presumed inherent inefficiency
of testing primeness.

 

[osmium]

I need the EFFICIENT algorithm for finding whether given number is
prime or not.

This is a whole mini-industry. Try searching for Rabin-Miller, for one
popular example.

If this is a school assignment, learn to phrase your questions more
carefully. You probably won't get an answer but at least you will be less
likely to get mis-directed into a jungle of stuff that is well beyond your
current needs and interests.

For example, efficient, even if capitalized, has no particular meaning in
the context you provided.

 

[Arctic Fidelity]

(e-mail address removed) wrote in @z14g2000cwz.googlegroups.com:

Hello,

I need the EFFICIENT algorithm for finding whether given number is
prime
or not.

There are sooo many algorithms for prime numbers out there, it's
rather hard to tell which one will best suit your needs. You should
probably try searching for "effecient prime algorithms" or something
of that nature online to find out more information about these.

 

[Dik T. Winter]

> (e-mail address removed) wrote:
> # Hello,
> #
> # I need the EFFICIENT algorithm for finding whether given number is
> # prime
> # or not.
>
> NSA needs one too. Many cipher systems depend on the presumed inherent inefficiency
> of testing primeness.

Testing primeness is reasonably efficient. It is factoring large number
that is difficult. With current software proving a 150 digit number
prime will take in the order of minutes. Factoring such a number will
take many months.

 

[websnarf]

I need the EFFICIENT algorithm for finding whether given number is
prime or not.

Try this:

http://www.pobox.com/~qed/primeat.zip

 

[Kevin D. Quitt]

Besides the other comments, it also depends on how large the number is.

 

[Don]

Hello,

I need the EFFICIENT algorithm for finding whether given number is
prime
or not.

Regards,
Ajay

#include <stdio.h>

/* This program implements a blindingly fast O(n^n) algorithm
to find prime numbers, using an elegant recursive method. */
int p(int n, int m, int d)
{
int i, r = m != n;
for(i=0; d && (i<n); i++) r *= p(n,i*m,d-1);
return r;
}

/*------------------------------------------
Determine if numbers are prime
--------------------------------------------*/
int main(int argc, char* argv[])
{
int n;
for(n = 2; n; n++)
printf("%d is%s prime\n",n, p(n,1,n)?"" : " not");
return 0;
}

 

[Felix Rawlings]

(e-mail address removed) wrote:
# Hello,
#
# I need the EFFICIENT algorithm for finding whether given number is
# prime
# or not.

NSA needs one too. Many cipher systems depend on the presumed inherent inefficiency
of testing primeness.

Really? Which ones? I doubt that they exist, because they would be
useless: probabilistic primality tests are extremely efficient. And,
anyway, last year a deterministic algorithm to do primality testing in
polynomial time was published.