Is there a better way to check whether a value is prime?

Question

In maths you would check whether an integer is prime by checking its divisibility by all prime numbers between 2 and sqrt(Z+), but "by all prime numbers" isn't practical, because you would also need to find all prime numbers between 2 and sqrt(Z+).

How would this be most practical in programming?

Base case in Python:
https://code.sololearn.com/c0jpOVjxATKt/?ref=app

I thought this would be little improved by putting a step of 2 after divisibility of 2 has been checked:

https://code.sololearn.com/cZAxZ8iOFddW/?ref=app

But is there something to make it better?

Answer 1

A variant of what you are saying is checking primality by so-called "wheels": Instead of stepping by 2, which only skips even numbers, you can step by varying amounts to also immediately skip multiples of 3:

Stepping by 4, then 2, then 4, then 2, then 4..., or, the "wheel" [4,2] gives the number sequence:

1,5,7,11,13,17,19,23,...

Which is all the numbers except multiples of 2 and 3 removed, so you have less numbers to check.

The next bigger wheel is [6,4,2,4,2,4,6,2] which yields

1,7,11,13,17,19,23,29,31,37,41,...

which is all the multiples of 5 removed aswell; even less numbers to check.

As you can see this method is closely related to the sieve of erasthotenes!

So into your code you would hardcode a big enough wheel and then check primality this way.

(PS: For completeness, this is not the most efficient algorithm, there are waay better—and trickier—ones like the miller-rabin test.)

Answer 2

If you don't want to reinvent the wheel, use sympy.isprime().

You can read more about it here:
https://docs.sympy.org/latest/modules/ntheory.html?highlight=isprime#sympy.ntheory.primetest.isprime

from sympy.ntheory.primetest import isprime

print(isprime(42)) # False

Answer 3

Seb TheS I haven't checked the maths but I think a wheel for the first `n` primes should have a length of around `e^n` so it gets impractical very quickly.

There's also diminishing returns because getting rid of all multiples of 2 instantly eliminates 50% of the number line, but getting rid of all mutiples of 11 for example eliminates not even 1/11 ≈ 9% of all numbers, but even less, because many multiples of 11 will also be multiples of 2 and will already have been taken care of by the smaller wheel.

So there's a sweet spot in terms of wheel size for sure. It probably depends on your usecase. Or of course use a better primality test altogether :P

But using even a small wheel does make a difference, speedwise, yeah.

(EDIT: going from a 2,3,5,7 wheel to a 2,3,5,7,11 wheel removes around 2.08% more numbers, maybe that's worth it, maybe not)

Answer 4

Schindlabua That's very interesting, but it doesn't seem practical atleast to use big wheels, that atleast might need more memory than the basecase, but could it be faster?

Answer 5

Diego I think isprime() function can be directly imported from sympy. Like this:

from sympy import isprime

Answer 6

In line 5, why x%2 (==0 is skipping... Is that intentionally?) for i also..

Answer 7

Jayakrishna Yes, by it i can split the amount of iterations to half.

I don't need to check number divisibility to 4, 6, 8, 10... when I know if it is already divisible by 2.

Answer 8

Seb TheS
No. Sry, I mean, Am taking about
why if x%i : only,
instead of if x%i==0 :
It give wrong output....

Answer 9

Jayakrishna Yes, also forget if x = 2, both fixed.

Answer 10

If you just need to find the prime numbers to 100, you can bypass the check by taking all the numbers and eliminating the multiples - and what is left, must be a prime number. Like this:

https://code.sololearn.com/csvfn5E0ruTd/?ref=app