Python is_prime and time consuming
Python: is_prime and time consuming
Function enhancement
Once i start solving projectEuler problems i notes that i need the prime numbers in most of cases, so I wrote a function called ‘is_prime’ and it works fine. Some time just to get all the primes in a given range takes some seconds, seconds in computer time means waiting a lot. With some other problems that we need to get the prime in large numbers my function looks slow, since I am not deep in math I search the net for a better way to get the primes or to check if a given number is prime or not.
Definition A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. wikipedia.org. So as I understand a prime number is not dividable by any other numbers, so my is_prime function is taking a number let’s say n= 13, and start a loop from 2 to n=13 if we fond a number that divide 13 then 13 is not a prime.
Here is the code:
def is_prime1(num):
for t in range (2, num):
if num % t == 0 :
return False
return True
The function is working fine and we can get the prime numbers, but as I mention above, if we have a large number or a wide range, this will take some time. After searching the web, I found some facts regarding the Prime Numbers:
1. The only even prime number is 2. (So any other even numbers are not prime)
2. If the sum of a number digits is a multiple of 3, that number can be divided by 3.
3. No prime number greater than 5 ends in/with 5.
OK, now I can first cut any range to half by not going through even numbers (if even false). Then, I will see if the number end with 5 or not (if end with 5 false),last I will do a summation of the digits in the number if the sum divide by 3 (if yes false), and if the number pass then i will take it in the loop from 5 to n, and if any number divide it we will return false.
Here is the code after the enhancement:def is_prime2(num):
if num %2==0 : # pass the even numbers.
return False
num_d= str(num) # if last digits is 5, then not prime
t= len(num_d)
if (num_d[t-1]) == 5 :
return False
tot = 0
for each in str(num):
tot = tot + int(each)
if tot % 3 == 0 : # if digits sum divide by 3, then not prime
return False
for t in range (3, num, 2):
if num % t == 0 :
return False
return True
I test both function on my laptop, for different number ranges, and use the time function to see the time delays with each one. Here is the results. If any one know better way to do this please drop it here. Or on My Twitter.
|
Follow me on Twitter..Leave a Reply
Taking pictures is not my main daily practices, but when i start playing with my camera, i really enjoy my self.
Thanks for visiting my Space..
Ali's Photography Space... 
So, I don’t know the fastest prime test, but there are a few prime facts that I’m aware of.
First, you can determine if a number is prime in O(log N) time if you consider that you only need to check up to the square root of N. In other words, if you want to check if 144 is prime, you only need to check up to 12 because any numbers larger than that will have to combine with a value that’s less then 12.
Also, there’s a whole class of probabilistic tests that are even faster like the Miller-Rabin primality test. These algorithms usually check “random” numbers against the value to test whether or not it’s composite. After several checks, you should be confident enough to say whether or not the value is prime.
Thanks Jeremy, I will read about the log.
Good way to reduce the time complexity of isPrime function. The complexity can be further reduced if we replace the sum of digits loop with ”tot = num % 9” and the range of factor check loop to (7, sqrt(num), 2).
Thanks for your add-on, I will check that ..