Reducing the running time in Python

Question

This Program checks how many prime integers between two ranges and their sum should also be prime. How can I reduce the running time?. HERE IS THE OPTIMIZED PRIME FUNC (eprime). BUT SILL IT EXCEEDES TIME WHICH IS 3 SEC HOW CAN I OPTIMIZE IT MORE? i really did my best but i cant find any other way.

import math
def eprime(num):
    if num < 2:
        return False
    if num % 2 == 0:
        return num == 2
    div = 3
    while div * div <= num:
        if num % div == 0:
            return False
        div += 2
    return True

x=input()
array=[]
count=0
counter=0
x=int(x)
for i in range(0,x):         # getting input from user and the ranges
    y=input().split()
    size=len(y)-1
    a=int((y[0]))
    b=int(y[size])+1

    for num in range(a,b):  # iterating on the ranges to check each number=prime?
        if eprime(num):
         num2=str(num)
         size3=len(num2)
         if(size3>=2):
          for j in range (0,size3):    # count= sum of num. if (11) then count=2
            count+=int(num2[j])
            num=count 
          if  eprime(num) and (num!=0):  # if count=prime then increment counter
            counter+=1

          count=0 
         else:
          counter+=1

    array.append(counter)
    counter=0
size2=len(array)
for i in range (0,size2):
   print(array[i])


////////////////////////////////////////////////////////////////   

Expected:

        sample input: 2
                      1 9
                      2 5
        sample output: 4
                       3

Answer 1

You are asking two questions which I will summarize below:

1. What is the fastest way for a primality test. Ans: Well, its a duplicate of this question. Check Alexandru's answer.

2. Why is your code not running for long ranges. Well check your identation. Its horrible. But look closely to this block of code.

(Near Line 33):

if  eprime(num)==True and (num!=0):
        counter+=1
        count=0

You are making the count 0 only if your number comes out to be prime. Well, this is wrong as in the next loop the count value will not be zero as it should be. This statement should be out of loop.

if  eprime(num)==True and (num!=0):
        counter+=1

    count=0

This fixes the problem.

My other thoughts:

1. Checkout this block of code:

(Near Line 29):

for j in range (0,size3):
         count+=int(num2[j])
         num=count   <-- Value assigned to `num` 



if  eprime(num)==True and (num!=0):
        counter+=1
        count=0 

But you have already defined num to the loop variable. for num in range(a,b): Now you are again assigning value to num. Why??

Though in your case this does not causes any problem, use as many variables as you like. Assign it to some other variable numx. Because it makes your code look nice and less chance of error.

2. You must always beautify your code and make is less lengthy before posting it to stackoverflow. This makes your question much more likable and easily answered.

Edit (How to make your primality check faster):

Your code is doing two major tasks:

1. Dividing a number by everything that is below that. e.g. 6 is divided by 2, 3, 4, and 5.
2. Adding the digits of numbers to check if their sum is prime or not.

The second point does not go through many loops, hence its safe to ignore that. (For now).

For the first point do the following:

1. You know that if something is divided by 2, then its a waste to check for 4, 6, 8, and so on. So straight away avoid checking for any even number.
2. Similarly if already the number is divisible by 3, there is no point in checking for 6, 9, and so on. The pattern in step 1 and 2 is that do not try and check the multiple of base numbers.
3. Only check till the square root of a number in a loop. E.g. if you are checking for number 40. Then square root of 40 is roughly 7. So if any number till 7 has not divided 40, then its guaranteed that any number after 7 will definitely not divide 40. So its pointless to go more than 7.

What I suggest is for you is to try and reduce the sample space by some degree. E.g. if your range is from 1 to 100, create a list which contains all numbers 1 to 100. Then start a loop and try to cross out some numbers from them. E.g. cross out 1, multiple of 2, 3, 5, 7 and more if you like. The more you add, the better becomes your chances because then you will only waste time doing equality tests rather than looping. In the end, the list in your hand will contain only those numbers which have greater chance of being a prime number. Infact if you are planning to run this program many times, you might consider pre-compiling your result for lets say 100,000 and just using this list in each of your run.

Then also apply rule number 3. This should make your program much faster than what it is today.

Point number 4 where it all becomes very serious: Now if you still want more power, note that your function to check for primality is independent from your program. i.e. you just pass it numbers and it gives you true false. Hence you can run this function in many threads and that should increase the speed of your program.