Finding n numbers common over N lists

Question

I am trying to solve this problem (from Project Euler).

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

For replicating the scenario, considering the fact that for 4 prime numbers of the interest (3,7, 109, 673)

1. 673 is the highest number with 673109 as the upper limit

I used seive of Erathosenes to generate prime number till 700000 and stored it in a list.

And derived prime number till 700 and stored it in another list .

Now,

l = [3,5,7,11 ...] -- till 700
primes = [3,5,.....] - till 700000

Now, I compared each number in the list with other prime numbers by adding prefix and suffix.

Take , 3 and compare it with 5 . 35 and 53 are not prime. then compare with 7 . 37 and 73 are prime. Hence insert 7 into list.

End of loop for 3, insert into a dictionary with 3 as key and list of numbers matching the property for 3 in list as Value . I also added the key value to the list.

Hence, I end up with a dictionary like this

key : 3 , Value : 3, 7, 11, ..., 109 , ... 673 
key : 7 , Value : 3, 7, 11, .., 109, 673
key : 11, Value : ......
..
..
.. 
key 673 , Value : 3,7, .. 109, 673 

Now, i have 123 lists, in which only 4 lists are having 3,7,109 and 673.

How do I retrieve the common numbers over those lists?

I don't know how to compare 4 lists for matching elements.

But, if there is some way where we can derive 4 numbers which are common in 4 lists, then I've solved the Project Euler problem. I can apply same logic for 5 numbers by increasing the upper limit.

My current code :

   def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

primes = list(eratosthenes2(700000))

def isReversedPrime(m,n):
    if( int( str(m) + str(n) ) in primes and int( str(n) + str(m) ) in primes ):
        return True
    else:
        return False

f1 = open('logs.txt', 'w+')


toCheck = list(eratosthenes2(700))
#toCheck = [ i for i in range(2,700)]
d = {}

print "Total Elements " , len(toCheck)
for i in range(len(toCheck)):
    print "Checking for ", toCheck[i], " iteration ", i
    l = []
    for j in range(len(toCheck)):
        if isReversedPrime(toCheck[i], toCheck[j]) == True :
            l.append(toCheck[j])
    #print toCheck[i] , " has " , len(l), " elements "
    if len(l) > 0:
        d[toCheck[i]] = l
    #print "\n"

Answer 1

You can use set.intersection to find common elements.

>>> list1 = set([1,2,3,4])
>>> list2 = set([2,3,4,5])
>>> list3 = set([3,4,5,6])
>>> lists = [list1, list2, list3]
>>> set.intersection(*lists)
set([3,4])