Re: [Phys-l] Search for Prime Numbers Generation Program

[Brian Whatcott <betwys1@sbcglobal.net>]

At 01:16 PM 11/6/2006, Roberto, you wrote:

> Hello:
>
> I apologize if my problem could be a little out of topic, but I am 
> dealing with prime number
> generation. Does somebody know a program to generate very large 
> prime numbers that can be
> shown to the students? (Perhaps there can be an open-code project). 
> Thanks very much.
>
> My best regards.
>
> Roberto


Hi Roberto,
I see you are posting from distant parts - is it Argentina?

I noticed that the responses to your question were a little thin
 which reminded me -
it's been years ago now since I was suggesting to the readers
 of this list how helpful it is to use a search engine.
Not just years ago - but last decade, last century - some
 previous millennium in fact - or so it seems.

One might once have tried Dogpile,   or some other agglomerator
 of web hits - but Google has long established a senior niche in the
search field.

It is also true that a certain proportion of contributors here are grumpy
old men - some retired even - though it is more sad to see faithful
contributors detaching themselves when retired. Which is to say,
the question may not have seemed  exciting to everyone.

Anyway, to a young mind, a prime number generator can be a fulfilling
achievement.    When IBM reps were casting round for ideas on making
 a home based computer in the seventies, I for one advocated the
incorporation of Basic.   That would be a way of writing some code
to list primes.


Still, enough reminiscing: a young person, armed only with the knowledge
 that a number is called prime that cannot be divided  by any whole
number smaller than itself other than one, may start with an exhaustive
 division of each ascending number in turn.

She might then easily deduce that only odd numbers should be candidates
 for primeness testing, for even numbers are divisible by two.

A next step in sophistication  might be in realizing that it is not 
necessary to
divide by all the  numbers less than the candidate, nor even by all the
odd numbers and two.

To get to this conclusion, one sees that a candidate may fail by dividing by
 some factor.   And if there is some biggish factor,  it will need 
to be multiplied
 by some smaller factor in order to make a candidate number fail.

In other words, there is a factor of maximal size which can possibly be
multiplied  by another factor of similar size to reach the size of the number
 under test.
And of course, that factor of max size is the next whole number greater
than the root of the test candidate.
Then one may save each prime in an array, and divide only by these,
but that too is an exhaustive method, which does not allow one to
start with an arbitrarily large candidate.

These are the elementary methods, and they are all quite unsuitable for
 your desire of working out prime numbers of many digits.

You will recall that the largest prime presently known has something less
than ten million digits - in fact, there is an appreciable prize ($100,000)
for setting out the next prime of ten million digits or more, if I recall.

But when I last did a Google search for
        prime number generator,
besides the down loadable code, there were the web based calculators
 - so let me find something for you now:

  <http://alumnus.caltech.edu/~chamness/prime.html>

 This one starts small, so there's not much danger of your winning
$100,000 with it.

  <http://bach.dynet.com/primes/>
 This has some sources,  a list of the primes less than 1,000,000
and means for finding primes of any length.

   <http://javaboutique.internet.com/prime_numb/>
This is the java code (down loadable) to find a number of primes above
 a given lower limit.

And fourth on the list of hits from Google is this Wikipedia entry,
 which I commend to you.
   <http://en.wikipedia.org/wiki/Prime_number>

(I expect you know already, but to get to the Google seach you go here:
   <http://www.google.com/> for these first four hits, and the
succeeding 1.6 million hits in the same vein.

Respectfully

Brian Whatcott,  Altus OK