Page 1 of 1 [ 4 posts ] 

Ganondox
Veteran
Veteran

User avatar

Joined: 7 Oct 2011
Age: 23
Gender: Male
Posts: 5,807
Location: USA

03 Jun 2013, 11:45 am

Image

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


Fnord
Veteran
Veteran

User avatar

Joined: 6 May 2008
Gender: Male
Posts: 42,055
Location: Stendec

03 Jun 2013, 12:14 pm

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.



eric76
Veteran
Veteran

User avatar

Joined: 31 Aug 2012
Gender: Male
Posts: 10,721
Location: In the heart of the dust bowl

03 Jun 2013, 2:06 pm

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.



Ganondox
Veteran
Veteran

User avatar

Joined: 7 Oct 2011
Age: 23
Gender: Male
Posts: 5,807
Location: USA

11 Jun 2013, 10:40 am

Fnord wrote:
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.


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.

eric76 wrote:
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.


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