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)
- 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
Post a Comment