Mercurial > cpython-lru_cache-weakref

annotate Demo/scripts/fact.py @ 54294:dba767bc3155 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove mention of old ctypes version
author Benjamin Peterson <benjamin@python.org>
date Sat, 23 May 2009 20:59:09 +0000
parents c0da7f2361ec
children 6587ea6d3e78
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4573
73758db2f464 /usr/local/bin/python -> /usr/bin/env python
Guido van Rossum <guido@python.org>
parents: 1269
diff changeset
1 #! /usr/bin/env python
274
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
504
eb03977baeeb Adapt to mixed-mode arithmetic, and added a warning comment.
Guido van Rossum <guido@python.org>
parents: 274
diff changeset
3 # Factorize numbers.
eb03977baeeb Adapt to mixed-mode arithmetic, and added a warning comment.
Guido van Rossum <guido@python.org>
parents: 274
diff changeset
4 # The algorithm is not efficient, but easy to understand.
eb03977baeeb Adapt to mixed-mode arithmetic, and added a warning comment.
Guido van Rossum <guido@python.org>
parents: 274
diff changeset
5 # If there are large factors, it will take forever to find them,
eb03977baeeb Adapt to mixed-mode arithmetic, and added a warning comment.
Guido van Rossum <guido@python.org>
parents: 274
diff changeset
6 # because we try all odd numbers between 3 and sqrt(n)...
274
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
7
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
8 import sys
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
9 from math import sqrt
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
10
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
11 def fact(n):
49168
c0da7f2361ec Update uses of string exceptions
Andrew M. Kuchling <amk@amk.ca>
parents: 49164
diff changeset
12 if n < 1: raise ValueError # fact() argument should be >= 1
32735
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
13 if n == 1: return [] # special case
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
14 res = []
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
15 # Treat even factors special, so we can use i = i+2 later
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
16 while n%2 == 0:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
17 res.append(2)
49164
41524f9e2a2f #687648 from Robert Schuppenies: use classic division.
Andrew M. Kuchling <amk@amk.ca>
parents: 33456
diff changeset
18 n = n//2
32735
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
19 # Try odd numbers up to sqrt(n)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
20 limit = sqrt(float(n+1))
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
21 i = 3
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
22 while i <= limit:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
23 if n%i == 0:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
24 res.append(i)
49164
41524f9e2a2f #687648 from Robert Schuppenies: use classic division.
Andrew M. Kuchling <amk@amk.ca>
parents: 33456
diff changeset
25 n = n//i
32735
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
26 limit = sqrt(n+1)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
27 else:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
28 i = i+2
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
29 if n != 1:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
30 res.append(n)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
31 return res
274
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
32
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
33 def main():
32735
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
34 if len(sys.argv) > 1:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
35 for arg in sys.argv[1:]:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
36 n = eval(arg)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
37 print n, fact(n)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
38 else:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
39 try:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
40 while 1:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
41 n = input()
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
42 print n, fact(n)
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
43 except EOFError:
2bc66f1df7cc Whitespace normalization. Ran reindent.py over the entire source tree.
Tim Peters <tim.peters@gmail.com>
parents: 4573
diff changeset
44 pass
274
12a64115a4ee Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
45
33456
487280cf71b9 Add 'if __name__ == "__main__":' to files already as a usable as a module.
Johannes Gijsbers <jlg@dds.nl>
parents: 32735
diff changeset
46 if __name__ == "__main__":
487280cf71b9 Add 'if __name__ == "__main__":' to files already as a usable as a module.
Johannes Gijsbers <jlg@dds.nl>
parents: 32735
diff changeset
47 main()