Mercurial > cpython-lru_cache-weakref

annotate Demo/scripts/fact.py @ 58925:eecf1bef052d 2.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged revisions 78207 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r78207 | ezio.melotti | 2010-02-17 01:26:09 +0200 (Wed, 17 Feb 2010) | 1 line #7930: fix stripid ........
author Ezio Melotti <ezio.melotti@gmail.com>
date Tue, 16 Feb 2010 23:29:44 +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()