#
Prime Number Algorithm

**1**of

**1**[ 4 posts ]

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.

_________________

Cinnamon and sugary

Softly Spoken lies

You never know just how you look

Through other people's eyes

Autism FAQs http://www.wrongplanet.net/postt186115.html

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.

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.

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.

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.

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.

_________________

Cinnamon and sugary

Softly Spoken lies

You never know just how you look

Through other people's eyes

Autism FAQs http://www.wrongplanet.net/postt186115.html

**1**of

**1**[ 4 posts ]

Similar Topics | |
---|---|

Number compression for prime number storage |
18 Apr 2013, 7:41 pm |

prime number today! |
25 Jan 2010, 11:47 am |

new prime number found |
02 Oct 2008, 8:13 am |

[Poll} What's your favorite prime number? |
20 Nov 2012, 12:40 pm |