But when I was in my first year in technical high school (first university year) in computer science, back in 1989-1990, I was given a homework assignment to implement a prime number algorithm in Pascal (I remember it was in Pascal, but it might have been in Basic or in C, the two other languages we had to work with at the time). My first implementation was just a standard Eratosthenes sieve just using odd numbers both for numbers to be examined and for candidate divisors (with a special case for 2, the only even number that is prime).
In that assignment, I then noticed that the algorithm was getting really slow when getting around the 1,000,000 mark (if I remember correctly the timing, hardware of the time was really not like today, especially with my budget PC then). So I offered at least two possible performance optimizations:
- discarding even numbers and multiples of 3;
- choosing possible divisors only among the primes found so far;
If I remember correctly, I obtained the maximum possible mark for that homework assignment.But if the real advantage of Algorithm3 is just discarding not only odd numbers but also multiples of 3, then I could almost claim to be a co-discoverer (I am of course just joking, I've never published on that, and I am fairly sure some other people thought about that possibility before). But, still, same idea, same period. And I am almost sure that I still have that assignment paper copy in my archives, with the annotations from my professor at the time (at least I still had it very recently, I don't think I have thrown it away in between).
I might try to post the Pascal abridged source code tomorrow, if I remember.
In reply to Re^2: The sieve of Xuedong Luo (Algorithm3) for generating prime numbers
by Laurent_R
in thread The sieve of Xuedong Luo (Algorithm3) for generating prime numbers
by marioroy
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |