python - Finding n numbers common over N lists -


i trying solve problem (from project euler).

the primes 3, 7, 109, , 673, quite remarkable. taking 2 primes , concatenating them in order result prime. example, taking 7 , 109, both 7109 , 1097 prime. sum of these 4 primes, 792, represents lowest sum set of 4 primes property.

find lowest sum set of 5 primes 2 primes concatenate produce prime.

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

  1. 673 highest number 673109 upper limit

i used seive of erathosenes generate prime number till 700000 , stored in list.

and derived prime number till 700 , stored in list .

now,

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

now, compared each number in list other prime numbers adding prefix , suffix.

take , 3 , compare 5 . 35 , 53 not prime. compare 7 . 37 , 73 prime. hence insert 7 list.

end of loop 3, insert dictionary 3 key , list of numbers matching property 3 in list value . added key value list.

hence, end dictionary 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, have 123 lists, in 4 lists having 3,7,109 , 673.

how retrieve common numbers on lists?

i don't know how compare 4 lists matching elements.

but, if there way can derive 4 numbers common in 4 lists, i've solved project euler problem. can apply same logic 5 numbers increasing upper limit.

my current code :

   def eratosthenes2(n):     multiples = set()     in range(2, n+1):         if not in multiples:             yield             multiples.update(range(i*i, n+1, i))  primes = list(eratosthenes2(700000))  def isreversedprime(m,n):     if( int( str(m) + str(n) ) in primes , int( str(n) + str(m) ) in primes ):         return true     else:         return false  f1 = open('logs.txt', 'w+')   tocheck = list(eratosthenes2(700)) #tocheck = [ in range(2,700)] d = {}  print "total elements " , len(tocheck) in range(len(tocheck)):     print "checking ", tocheck[i], " iteration ",     l = []     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" 

you can use set.intersection 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]) 

Comments

Popular posts from this blog

twig - Using Twigbridge in a Laravel 5.1 Package -

jdbc - Not able to establish database connection in eclipse -

firemonkey - How do I make a beep sound in Android using Delphi and the API? -