Prime Number Algorithm

Post Reply New Topic

This algorithm sorts numbers based on their lowest prime number and finds new primes in the process. Basically, it has a row for each prime number, it tests if each number is in the chart, if it's not it adds a new prime number, and afterwards it adds the next number in the same row to the chart.

Keep in mind that when two prime integers are multiplied to produce a third number, at least one of the original two prime integers will be equal to or less than the square root of the product, and neither will be an integer that is greater than half of the product.

Thus, you can reduce the time spent testing prime root integers if their values do not exceed the value of the square root of the product.

That diagram is too blurry to read.

If I was going to create a list of prime numbers, I'd go with the Sieve of Eratosthenes.

One way is to represent each number with a single bit and don't include the even numbers. Think of it as an enormous array of bits where bit 0 represents the number 3, bit 1 the number 5, bit 2 the number 7, ... . Then with N bytes, you could efficiently find all prime numbers between 3 and N*16+1.

Yeah, I realize it can be made more effective, when each new prime is found the algoritm really should go down a slightly different path before it goes back to the main one, but I wanted to show the basic principle. The actual mechanics for searching the array are also not shown.



Sorry about that, it's possible to read, but only barely. The text description is the best hint. Anyway, this is based upon the sieves concept, but remodeled so it works a bit differently and has a slightly different purpose. This really shows were the sieve catches each number.