Ali's Photography Space…

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):

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.