+ 3

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

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?

15th Feb 2020, 11:27 AM
Seb TheS
Seb TheS - avatar
10 Respuestas
+ 7
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.)
15th Feb 2020, 11:51 AM
Schindlabua
Schindlabua - avatar
+ 4
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
15th Feb 2020, 3:30 PM
Diego
Diego - avatar
+ 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)
15th Feb 2020, 12:15 PM
Schindlabua
Schindlabua - avatar
+ 1
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?
15th Feb 2020, 12:04 PM
Seb TheS
Seb TheS - avatar
+ 1
Diego I think isprime() function can be directly imported from sympy. Like this: from sympy import isprime
16th Feb 2020, 3:30 AM
Ishmam
Ishmam - avatar
0
In line 5, why x%2 (==0 is skipping... Is that intentionally?) for i also..
15th Feb 2020, 12:12 PM
Jayakrishna 🇮🇳
0
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.
15th Feb 2020, 12:15 PM
Seb TheS
Seb TheS - avatar
0
Seb TheS No. Sry, I mean, Am taking about why if x%i : only, instead of if x%i==0 : It give wrong output....
15th Feb 2020, 12:20 PM
Jayakrishna 🇮🇳
0
Jayakrishna Yes, also forget if x = 2, both fixed.
15th Feb 2020, 12:22 PM
Seb TheS
Seb TheS - avatar
0
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
17th Feb 2020, 7:01 AM
Darina
Darina - avatar