Return to Question

Last semester in my Masters Program I developed this code for sieving.

Is this any decent? Or is my implementation really slow?

My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, despite coming up with my algorithm without doing any research other than the bare numbers.

Edit:

I guess I should explain the algorithm a bit to those who are interested. Essentially it skips over a large percentage of numbers (I estimate about 66%). It skips all factors of 2 and 3. The first loop throws in primes and potential primes through a modified formula of 6k+-1. The second nested loop takes the outer prime numbers and finds all multiples.

The inner if statement skips numbers as well - if the number is a factor of 3, it skips ahead. For instance if B = 13, B+2 = 15%3 = 0, then B jumps straight to 17. I've found this method to be faster for some reason than accessing the array every b+=2; and switching the boolean. Unfortunately, I wish I could find a way to make it more efficient (I may be able to use an additional counter to just figure out when the number is going to fall on a five or three).

Psuedo-code as follows (of course this implementation is different, but follows similar principles):

1. Initialize list with initial values (2,3).
2. Use the formula 6k±1 where k = 1 and must increment by 1. Store values to list.
3. Compute step 2 up to a product n, where n > 7 if k = 1.
4. Starting with x=5, remove all products of x*y (to n), where y starts at x and
   increments to the next number in the list as x remains the same.
5. Repeat step four by assigning x to the next number in the list - stop when x*y > N.
6. Final step: We must remove all factors of the square of every prime number (25, 49)

Last semester in my Masters Program I developed this code for sieving. My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, despite coming up with my algorithm without doing any research other than the bare numbers.

Essentially it skips over a large percentage of numbers (I estimate about 66%). It skips all factors of 2 and 3. The first loop throws in primes and potential primes through a modified formula of 6k+-1. The second nested loop takes the outer prime numbers and finds all multiples.

The inner if statement skips numbers as well - if the number is a factor of 3, it skips ahead. For instance if B = 13, B+2 = 15%3 = 0, then B jumps straight to 17. I've found this method to be faster for some reason than accessing the array every b+=2; and switching the boolean. Unfortunately, I wish I could find a way to make it more efficient (I may be able to use an additional counter to just figure out when the number is going to fall on a five or three).

Psuedo-code as follows (of course this implementation is different, but follows similar principles):

1. Initialize list with initial values (2,3).
2. Use the formula 6k±1 where k = 1 and must increment by 1. Store values to list.
3. Compute step 2 up to a product n, where n > 7 if k = 1.
4. Starting with x=5, remove all products of x*y (to n), where y starts at x and
   increments to the next number in the list as x remains the same.
5. Repeat step four by assigning x to the next number in the list - stop when x*y > N.
6. Final step: We must remove all factors of the square of every prime number (25, 49)

Is this any decent, or is my implementation really slow?

Edit:

Newly Updated Code here A fast approach to prime number sieving (non-threaded array)

Original Thread

Last semester in my Masters Program I developed this code for sieving.

Last semester in my Masters Program I developed this code for sieving.

Edit: Newly Updated Code w alternate and more efficient algorithm matching pseudo code in separate answer in this thread.

Edit:

Newly Updated Code here A fast approach to prime number sieving (non-threaded array)

Original Thread