Time_2-time_1 # 0.9901950359344482 secondsįor a 100 thousand numbers, using sieves is more than 12 times faster. Sieve = False #because we wont consider zero and one as primes To get a list of primes you can use ]įor ind in range(3,int(math.sqrt(number))+1):
So if you want to check if a number is prime, you can simple use sieve. So if we divide a number by integers till the ceiling of its square root and its still indivisible, that means its a prime. Why so? Because a number can't have two factors both of which are greater than the square root of the number. Additionally, to optimize, we iterate only to the square root of 1 million.
We will iterate over every number to one million and mark every multiple of it as False in the sieve list. The idea is that we initially create a list called sieve and assign all values to True which means that we are for now considering all numbers to 1 million(inclusive) as primes. Here's how to get all the primes upto one million. The easiest way to do this is to use something called as Sieve.
0 kommentar(er)
