166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#!/usr/bin/env python2.6 266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# Copyright (C) 2011 The Android Open Source Project 466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# Licensed under the Apache License, Version 2.0 (the "License"); 666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# you may not use this file except in compliance with the License. 766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# You may obtain a copy of the License at 866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# http://www.apache.org/licenses/LICENSE-2.0 1066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 1166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# Unless required by applicable law or agreed to in writing, software 1266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# distributed under the License is distributed on an "AS IS" BASIS, 1366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# See the License for the specific language governing permissions and 1566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# limitations under the License. 1666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 1766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 1966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# Generates a table of prime numbers for use in BasicHashtable.cpp. 2066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 2166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# Each prime is chosen such that it is a little more than twice as large as 2266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# the previous prime in the table. This makes it easier to choose a new 2366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# hashtable size when the underlying array is grown by as nominal factor 2466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# of two each time. 2566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown# 2666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 2766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Browndef is_odd_prime(n): 2866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown limit = (n - 1) / 2 2966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown d = 3 3066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown while d <= limit: 3166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if n % d == 0: 3266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return False 3366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown d += 2 3466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return True 3566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 3666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownprint "static size_t PRIMES[] = {" 3766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 3866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownn = 5 3966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownmax = 2**31 - 1 4066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownwhile n < max: 4166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown print " %d," % (n) 4266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown n = n * 2 + 1 4366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown while not is_odd_prime(n): 4466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown n += 2 4566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 4666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownprint " 0," 4766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownprint "};" 48