scraplasas.blogg.se - Make a list of prime numbers

I will not get into details on which method to generate all the primes to max(lista), or the prime check. If there are a lot, smaller elements, the 2nd method is faster, for a few, larger elements, method 1 will be better. Which of the 2 options is better depends on lista.

You generate all primes to max(lista), and then check whether all elements from lista are in those primes.

You test each element in lista with a faster prime tester.

You even unnecessarily instantiate this range to a list. So if you know what the largest number is which you need to check, checking against a set that is computed only once is the fastest.įor each number in lista, you iterate over the range(3, int(sqrt(n)+1), 2). of 7 runs, 10 loops each)Ĩ23 µs ± 9.53 µs per loop (mean ± std. of 7 runs, 10 loops each)ħ0.9 ms ± 235 µs per loop (mean ± std.

of 7 runs, 10 loops each)Ħ7.8 ms ± 706 µs per loop (mean ± std. On my machine all of these are faster than your original function: primes_list = list(prime_sieve(100000))ħ7.3 ms ± 373 µs per loop (mean ± std. Return len(primes_set & lista_set) = len(lista_set) """Check if all numbers in `lista` are primes."""Īnother alternative is to compute a set of primes once and then just check if all of them are in this set: primes_set = set(prime_sieve(100000)) Return all(n % x for x in range(3, int(sqrt(n) + 1), 2)) Uses exhaustive search to look for factors up to sqrt(n) + 1. Return all(n = 2 or (n % 2 and all(n % x for x in range(3, int(sqrt(n)+1), 2))) for n in lista)īut if you really want to make it more readable, you should factor out the prime check into another function: from math import sqrt This has the advantage that the range does not get consumed into a list which makes this stop generating values as soon as a value is found not to be prime.

You could pull out the special case of 2 in all(n % x for x in list(range(3, int(sqrt(n)+1), 2))+ ) by doing (n % 2 and all(n % x for x in range(3, int(sqrt(n)+1), 2))).There are a few obvious improvements, which either make it more readable or even faster: