summaryrefslogtreecommitdiffstats
path: root/libutils/primes.py
diff options
context:
space:
mode:
authorThe Android Open Source Project <initial-contribution@android.com>2013-11-22 11:28:10 -0800
committerConley Owens <cco3@android.com>2013-11-22 13:44:43 -0800
commit66ed50af6870210ce013a5588a688434a5d48ee9 (patch)
treea879f3ea31083496d0efe491bc187b6e0ebada39 /libutils/primes.py
parentdd2ac3de625e6c0328a0f70530d8ade0d2151bfc (diff)
parent536dea9d61a032e64bbe584a97463c6638ead009 (diff)
downloadsystem_core-66ed50af6870210ce013a5588a688434a5d48ee9.zip
system_core-66ed50af6870210ce013a5588a688434a5d48ee9.tar.gz
system_core-66ed50af6870210ce013a5588a688434a5d48ee9.tar.bz2
Merge commit '536dea9d61a032e64bbe584a97463c6638ead009' into HEAD
Change-Id: I5c469a4b738629d99d721cad7ded02d6c35f56d5
Diffstat (limited to 'libutils/primes.py')
-rwxr-xr-xlibutils/primes.py47
1 files changed, 47 insertions, 0 deletions
diff --git a/libutils/primes.py b/libutils/primes.py
new file mode 100755
index 0000000..e161dd8
--- /dev/null
+++ b/libutils/primes.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python2.6
+#
+# Copyright (C) 2011 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+#
+# Generates a table of prime numbers for use in BasicHashtable.cpp.
+#
+# Each prime is chosen such that it is a little more than twice as large as
+# the previous prime in the table. This makes it easier to choose a new
+# hashtable size when the underlying array is grown by as nominal factor
+# of two each time.
+#
+
+def is_odd_prime(n):
+ limit = (n - 1) / 2
+ d = 3
+ while d <= limit:
+ if n % d == 0:
+ return False
+ d += 2
+ return True
+
+print "static size_t PRIMES[] = {"
+
+n = 5
+max = 2**31 - 1
+while n < max:
+ print " %d," % (n)
+ n = n * 2 + 1
+ while not is_odd_prime(n):
+ n += 2
+
+print " 0,"
+print "};"