Feb 14, 2013, 3:52 PM
Post #7 of 7
OK, to many of us, "looking for a list of the first 100 prime numbers" really sounds like homework as it is such a classical assignment in general programming, basic algorithmic theory and (whatever specific) language learning, that we tend to react this way. I remember distinctly having homework assignments to write a Pascal and a C programs for generating the first 1,000,000 prime numbers (or maybe, all the prime numbers below 1,000,000, I am not sure). I loved it and I made numerous successive performance improvements (such as discarding even numbers above 2 before doing any calculations, and then aslo discarding multiples of 3, 5 and 10, etc.). The most efficient improvement, I remember that vividly althouh it was more than 20 years ago, was to store the primes that I found in an array, so that I would check for divisibility of new numbers only against primes in my array (up to square root of the number). I also remember that I got the best possible mark on this assignment. Son to make a long story short, looking for pirme numbers awfully sounds like a homework assignment.
Re: [oldrob] beginner prime number script
[In reply to]
But I must say that when I decided that I wanted to learn Perl, and this had nothing to do with my studies (it was years later), I also tried, among many other things, to find prime numbers. So that I understand what you are trying to do here. (And I also dit it in other languages).
In terms of algorithmics, there are two basic ways:
- check, for each number in a list, if it can be divided by a smaller number (the performance improvement being basically: if it can be divided by another prime number smaller than square root of that number);
- Eratosthene's sieve: prepare a list of numbers, iterate over a list of prime numbers, and cross out in the first list all numbers that are multiples of the primes.
The most efficient method is likely to be a combination of both methods. For instance, the method I used for the assignment described above was essentially based on the first one, but the idea of skipping immediately even numbers or multiples of 3, 5 and 10 is closer to an application of Erathosthene's sieve method.