Program not faster when checking much less numbers for finding primes-CodePudding

I made a program to find primes below a given number.

number = int(input("Enter number: "))
prime_numbers = [2]  # First prime is needed.
for number_to_be_checked in range(3, number   1):  
    square_root = number_to_be_checked ** 0.5
    for checker in prime_numbers:  # Checker will become every prime number below the 'number_to_be_checked'
        # variable because we are adding all the prime numbers in the 'prime_numbers' list.
        if checker > square_root:
            prime_numbers.append(number_to_be_checked)
            break
        elif number_to_be_checked % checker == 0:
            break
print(prime_numbers)

This program checks every number below the number given as the input. But primes are of the form 6k ± 1 only. Therefore, instead of checking all the numbers, I defined a generator that generates all the numbers of form 6k ± 1 below the number given as the input. (I added 3 also in the prime_numbers list while initializing it as 2,3 cannot be of the form 6k ± 1)

def potential_primes(number: int) -> int:
    """Generate the numbers potential to be prime"""
    # Prime numbers are always of the form 6k ± 1.
    number_for_function = number // 6
    for k in range(1, number_for_function   1):
        yield 6*k - 1
        yield 6*k   1

Obviously, the program should have been much faster because I am checking comparatively many less numbers. But, counterintuitively the program is slower than before. What could be the reason behind this?

CodePudding user response：

Using nested for loop along with square root will be heavy on computation, rather look at Prime Sieve Algorithm which is much faster but does take some memory.

CodePudding user response：

One way to use the 6n±1 idea is to alternate step sizes in the main loop by stepping 2 then 4. My Python is not good, so this is pseudocode:

function listPrimes(n)
  // Deal with low numbers.
  if (n < 2) return []
  if (n = 2) return [2]
  if (n = 3) return [2, 3]

  // Main loop
  primeList ← [2, 3]
  limit ← 1   sqrt(n) // Calculate square root once.
  index ← 5           // We have checked 2 and 3 already.
  step ← 2            // Starting step value: 5   2 = 7.
  
  while (index <= limit) {
    if (isPrime(index)) {
      primeList.add(index)
    }
    index ← index   step
    step ← 6 - step      // Alternate steps of 2 and 4
  }
  
  return primeList
end function

CodePudding user response：

In every 6 numbers, 3 are even and 1 is a multiple of 3. The other 2 are 6-coprime, so are potentially prime.

6k 0    6k 1    6k 2    6k 3    6k 4    6k 5
even            even            even
3x                      3x

For the 3 evens your primality check uses only one division (by 2) and for the 4th number, two divisions. In all, 5 divisions that you wish to skip.

But each call to a generator has its cost too. If you just replace the call to range with the call to create your generator, but leave the other code as is(*), you are not realizing the full savings potential.

Why? Because (*)if that's the case, while you indeed test only 1/3 of the numbers now, you still test each of them by 2 and 3. Needlessly. And apparently the cost of generator use is too high.

The point to this technique known as wheel factorization is to not test the 6-coprime (in this case) numbers by the primes which are not their divisors, by construction.

Thus, you must start with e.g. prime_numbers = [5,7] and use it in your divisibility testing loop, not all primes, which start with 2 and 3, which you do not need.