p200

p200.py

def fermat_primality_test(n):
    if pow(4, n - 1, n) == 1 and pow(6, n - 1, n) == 1:
        return True
    return False

def prime_proof_checker(x):
    og = list(str(x))
    number = list(str(x))
    prime_proof = True  
    for pos in range(len(number)):
        if pos == 0:
            for x in range(1, 10):
                number[pos] = str(x)
                if fermat_primality_test(int("".join(number))):
                    prime_proof = False  
        else:
            for x in range(0, 10):
                number[pos] = str(x)
                if fermat_primality_test(int("".join(number))):
                    prime_proof = False
        number[pos] = og[pos]
        if prime_proof == False:
            return False
    return True
    
def string_checker(x):
    if "200" in str(x):
        if prime_proof_checker(x):
            return True
    return False
    
def compute(limit):
    primes = list_primes(10**8)
    candidates = []
    count = 0
    for a in range(len(primes)):
        for b in range(a + 1, len(primes)):
            
            p = primes[a]
            q = primes[b]
            
            x = p*p*q*q*q
            y = p*p*p*q*q
            if x > limit and y > limit:
                break
            
            if x < limit:
                if string_checker(x):
                    candidates.append(x)
                    count += 1
                    print(x, count)
            
            if y < limit:
                if string_checker(y):
                    candidates.append(y)
                    count += 1
                    print(y, count)
            
    candidates = sorted(candidates)
    return candidates[199]