The next prime is 5, so 10, 15, 20, 25 and 30 are crossed out. Next 3 is identified as prime, then 6, 9, 12, 15, 18, 21, 24, 27 and 30 are crossed out. Then repeatedly take the smallest uncrossed number and cross out all of its multiples the numbers that remain uncrossed are prime.įor example, consider the numbers less than 30.
Full list of prime numbers trial#
Instead of trial division, a better approach, invented by the Greek mathematician Eratosthenes over two thousand years ago, is to sieve by repeatedly casting out multiples of primes.īegin by making a list of all numbers from 2 to the maximum desired prime n. Need to check with even numbers, so 'i' value can be start with 3 and Like so: import mathĪs in the first loop odd numbers are selected, in the second loop no You can improve it a little more by incrementing the range you check by 2, and thereby only checking odd numbers.
If all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):įor small numbers like 101 it doesn't matter, but for 10**8 the difference will be really big. You can write the same much shorter and more pythonic: for num in range(2,101):Īs I've said already, it would be better to check divisors not from 2 to n-1, but from 2 to sqrt(n): import math If n is divisible by any of the numbers, it is not prime.
You need to check all numbers from 2 to n-1 (to sqrt(n) actually, but ok, let it be n).
0 kommentar(er)
