1 #!/usr/bin/env python2.6 2 # 3 # Copyright (C) 2011 The Android Open Source Project 4 # 5 # Licensed under the Apache License, Version 2.0 (the "License"); 6 # you may not use this file except in compliance with the License. 7 # You may obtain a copy of the License at 8 # 9 # http://www.apache.org/licenses/LICENSE-2.0 10 # 11 # Unless required by applicable law or agreed to in writing, software 12 # distributed under the License is distributed on an "AS IS" BASIS, 13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 # See the License for the specific language governing permissions and 15 # limitations under the License. 16 # 17 18 # 19 # Generates a table of prime numbers for use in BasicHashtable.cpp. 20 # 21 # Each prime is chosen such that it is a little more than twice as large as 22 # the previous prime in the table. This makes it easier to choose a new 23 # hashtable size when the underlying array is grown by as nominal factor 24 # of two each time. 25 # 26 27 def is_odd_prime(n): 28 limit = (n - 1) / 2 29 d = 3 30 while d <= limit: 31 if n % d == 0: 32 return False 33 d += 2 34 return True 35 36 print "static size_t PRIMES[] = {" 37 38 n = 5 39 max = 2**31 - 1 40 while n < max: 41 print " %d," % (n) 42 n = n * 2 + 1 43 while not is_odd_prime(n): 44 n += 2 45 46 print " 0," 47 print "};" 48
