Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
Posts:
791
Registered:
9/1/10
|
|
A Way to Find Prime Numbers
Posted:
Sep 29, 2011 8:50 AM
|
|
One method to determine whether a number is prime is to divide by all
primes less than or equal to the square root of the number. If any of
the divisions come out as an integer, then the original number is
composite. Otherwise, it is a prime. One may omit actual calculation
of the square root; once one sees the quotient is less than the
divisor, stop. To be precise the last prime factor possible for some
number N is Prime(m) where Prime(m + 1) squared exceeds N.
The number of prime numbers less than N is near
\frac {N}{\ln N - 1}.
So, to check N for primality the largest prime factor is just less
than \scriptstyle\sqrt{N}, and so the number of such prime factor
candidates is close to
\frac {\sqrt{N}}{\ln\sqrt{N} - 1}.
This increases ever more slowly with N, but, because there is interest
in large values for N, the count is large also: for N = 10^20 it is
450 million.
|
|
|
|
