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