Proving your computer: Erastosthenes Sieve.

Anything you want to discuss about your vintage computer, or accessories for it, from general usage to advanced modding.

Proving your computer: Erastosthenes Sieve.

Postby Trygve » Mon Jun 20, 2005 12:26 pm

How fast IS your computer really?
Or better yet, how fast is the default programming language for it?

Quite simply, write a program in assembler which finds Prime numbers based on Eratosthenes Sieve:

The Sieve of Eratosthenes identifies all prime numbers up to a given number n as follows:

1. Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
2. Mark the number 1 as special (it is neither prime nor composite).
3. Set k=1. Until k exceeds or equals the square root of n do this:
-Find the first number in the list greater than k that has
- not been identified as composite. (The very first number
- so found is 2.) Call it m. Mark the numbers

- 2m, 3m, 4m, ...

- as composite. (Thus in the first run we mark all even
numbers greater than 2. In the second run we mark
all multiples of 3 greater than 3.)
- m is a prime number. Put it on your list.
- Set k=m and repeat.

4. Put the remaining unmarked numbers in the sequence on your list of prime numbers.

Write the program in the most common programming language for your computer, WITHOUT using assembly language.
If it has a 'compute mode' which speeds it up, feel free to use it, but...

In this program, all the primes must be listed on the screen as they are found(yes, the contents will scroll off the bottom, but that doesn't matter).
All Primes MUST IF POSSIBLE also be stored in some form of array or variables that can be read out afterwards.

To make it fun, on computers that are capable of it, this will be a 16bit challenge. That's right, from 1 to 65535. The deciding factor here isn't how many bits the processor is, but what the programming language accepts.

Any variation on the original concept is OK, as long as the starting conditions are the same.

Post full source and the time it took to run in a separate thread in this forum. (Time should be measured to the second if possible)

If you decide to do something 'drastic' in the program, please PM me beforehand so that I can either OK or nix it.

When(or if) you have a result, PM me and I'll add the result to this thread.

If you can redesign an already posted program and make it faster, by all means do so, and I'll update the results.

PS: I have a lot of computers, so will be able to test many programs myself, and trying to cheat... probably isn't a good idea.
User avatar
Über Geek
Posts: 108
Joined: Sun Jun 19, 2005 9:49 pm
Location: Norway

Return to General computer talks

Who is online

Users browsing this forum: No registered users and 1 guest