Generating numbers that are a product of consecutive primes

Question

I have implemented a correct but horribly coded solution to Project Euler Problem 293.

An even positive integer N will be called admissible, if it is a power of 2 or its distinct prime factors are consecutive primes. The first twelve admissible numbers are 2,4,6,8,12,16,18,24,30,32,36,48.

If N is admissible, the smallest integer M > 1 such that N+M is prime, will be called the pseudo-Fortunate number for N.

For example, N=630 is admissible since it is even and its distinct prime factors are the consecutive primes 2,3,5 and 7. The next prime number after 631 is 641; hence, the pseudo-Fortunate number for 630 is M=11. It can also be seen that the pseudo-Fortunate number for 16 is 3.

Find the sum of all distinct pseudo-Fortunate numbers for admissible numbers N less than 10⁹.

I use several nested loops that I wish to make into some nicer functions or such. The following is the first three sections of the code, out of 10 sections required to solve the problem. Each has one more nested loop, and while the time is not an issue I would like to improve this code, but I am not sure how to implement this algorithm in a more concise manner.

What the nth section does is generate all numbers less than 1e9, that contain only the first n prime numbers(and then add numbers relating to the problem to a set).

I have tried for example to have a list of exponents for all primes, and incrementing the outermost nonzero exponent, and then backtracking when the product is larger than 1e9, however I have not been able to do anything successful.

pseudofortunate=set()

pr=generate_primes(24)




num1=1
while num1<1e9/2:
    num1*=pr[0]
    num2=num1
    while num2<1e9/3:
        num2*=pr[1]
        m=num2+3
        while True:
            if is_prime(m):
                pseudofortunate.add(m-num2)
                break
            m+=2


num1=1
while num1<1e9/2:
    num1*=pr[0]
    num2=num1
    while num2<1e9/3:
        num2*=pr[1]
        num3=num2
        while num3<1e9/5:
            num3*=pr[2]
            m=num3+3
            while True:
                if is_prime(m):
                    pseudofortunate.add(m-num3)
                    break
                m+=2


num1=1
while num1<1e9/2:
    num1*=pr[0]
    num2=num1
    while num2<1e9/3:
        num2*=pr[1]
        num3=num2
        while num3<1e9/5:
            num3*=pr[2]
            num4=num3
            while num4<1e9/7:
                num4*=pr[3]
                m=num4+3

                while True:
                    if is_prime(m):
                        pseudofortunate.add(m-num4)
                        break
                    m+=2

Answer 1

Ok so I figured this one out, by doing the nested loops recursively as a generator. Below is a MUCH nicer code that yields the same answer.

def loop(n,depth):
    """generates numbers containing "depth" primes, up to n"""
    if depth==0:            #generates the powers of two
        num1=1    
        while num1<n/2:
            num1*=pr[0]
            yield num1
    else:
        for i in loop(n,depth-1):           #generates all numbers containing the first n prime numbers
            num_depth=i                     #number containing all previous primes
            while num_depth<n/pr[depth]:
                num_depth*=primes[depth]            #successively multiplies the nth prime
                yield num_depth

def admissiblenums(n=1e9):
    """generates a set of all admissible numbers not exceeding 1e9"""
    admissibleset=set()
    for i in range(len(pr)):
        nth_admissible_prime=set(loop(n,i))
        admissibleset|=nth_admissible_prime     #union of admissibles up to nth prime   
    return admissibleset


def pseudofortunate(n):
    """returns the pseudofortunate number of n
    (the difference between n, and the first prime larger than or equal to n)"""
    prime_candidate=n+3#defined as prime larger than n+1, so starting the search for a prime at n+3, since admissible numbers are always even
    while True:
        if is_prime(m):
            return prime_candidate-n        #returns the difference(pseudo-fortunate number) if prime_candidate is prime
        prime_candidate+=2      #check odd numbers
t1=time()
primes=generate_primes(24)      #the primes less than 24, since the primorial needs to be less than 1e9
pseudofortunates=set()      
for i in admissiblenums():
    pseudofortunates.add(pseudofortunate(i))    #adds psuedo-fortunate numbers to set
print sum(pseudofortunates)     #sum of unique pseudo-fortunate numbers
t2=time()
print t2-t1