Searching for pairs of integers that satisfy primality and divisibility conditions I wrote a program in Python 3 to check all tuples of the form (s,t) where s and t are positive integers satisfying three conditions:


The inequalities s &lt;= t^2 and t &lt;= s^2 hold, and the value s+t divides st(s+1)(t+1);
The value of s+1 is prime;
The inequalities both s * [math.ceil( math.ceil( (t^2)/(s+1) ) * ((s+1)/t) )] &gt; s(s+t) and s &gt; t hold.


I'm interested in how often a tuple (s,t) satisfies each of these conditions in turn; that is, how often a tuple meets condition (1), versus meeting both (1) and (2), versus meeting (1) - (3).

import math

def IsPrime(n):
# This returns True if a number is prime, and False if the number is composite.
    if n % 2 == 0 and n &gt; 2: 
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2)) 

def IsGQ(s,t):
# This checks the divisibility condition.
    return (s*t*(s+1)*(t+1)) % (s+t) == 0 and s &lt;= t**2 and t &lt;= s**2

def IsNotTransitive(s,t):
    n = math.ceil((t**2)/(s+1))
    k = math.ceil(n*((s+1)/t))
    return (s*k) &gt; t*(t+s) and s &gt; t

rng = 1000 # The upper limit that `t` will iterate up to
quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) and (2) 
prime_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (3) 
intransitive_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (4)

# The next 5 lines place all prime numbers up to rng^2 into a list. 
# Ideally, this cuts down on how many times s+1 has to be checked to be a prime.
primes = [] 
for i in range(1, rng**2):
    if IsPrime(i):
        primes.append(i)

for t in range(4, rng + 1): # Due to project details, I don't care about t&lt;4. 
    if t % 50 == 0: 
        print("We have reached t = " + str(t) + ".")
    for s in range(2, t**2 + 1): # To satisfy condition (1), I don't want s to iterate above t^2
        if IsGQ(s,t): # Condition (1) and (2)?
            quads += 1
            if s+1 in primes:            # Condition (3)?
                prime_quads += 1
                if IsNotTransitive(s,t): # Condition (4)?
                    intransitive_quads += 1

print(str(quads))
print(str(prime_quads))
print(str(intransitive_quads))  


Currently, this runs to completion in over 10 minutes for rng = 1000. Ideally, running this for rng = 10000 in a reasonable amount of time is my current goal; computing these numbers for the value rng = 100000 is my most optimistic goal.

Is there any way to reorder my iteration or change my method of checking for primeness that could be more efficient? It seems that the time for s+1 in primes to complete grows quadratically with rng. Since, after a certain point, s+1 will be less than every value in primes that hasn't been checked yet, would it be better to write my own "in" function along the lines of

def CheckPrime(s, primes):
    for n in primes:
        if s+1 == n:
            return True
        elif s+1 &lt; n:
            return False


or would this still be slower than the current code?

Note: IsPrime comes from this Stack Overflow answer.
You are running into several performance problems.

First: if you want to generate a list of primes, you should use a sieve which is much more efficient.

Second: you are checking s+1 in primes, which is inefficient for a list. Instead you should make primes be a set, so that your lookup time is constant.
Third: Instead of for s in range(2, t**2 + 1):, you should use for s in range(floor(t**.5), t**2 + 1):, as this prevents wasting time checking values where s^2&lt;t.

Between these two changes you should see a pretty large speed boost.