{VERSION 6 0 "IBM INTEL NT" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 3 3 1 0 1 0 2 2 15 2 }{PSTYLE "Title" -1 256 1 {CSTYLE "" -1 -1 "Times " 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 } {PSTYLE "Author" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {PARA 256 "" 0 "" {TEXT -1 64 "Testing for prime numbers and f actoring into a product of primes" }}{PARA 257 "" 0 "" {TEXT -1 11 "Dw ight Lahr" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 65 "The function \"isprime,\" how it works (from the Help descripti on):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 15 "" 0 "" {TEXT -1 67 " The function isprime is a probabilistic primality testing routine. " } }{PARA 15 "" 0 "" {TEXT -1 490 "It returns false if n is shown to be c omposite within one strong pseudo-primality test and one Lucas test an d returns true otherwise. If isprime returns true, n is ``very probabl y'' prime - see Knuth ``The art of computer programming'', Vol 2, 2nd \+ edition, Section 4.5.4, Algorithm P for a reference and H. Reisel, ``P rime numbers and computer methods for factorization''. No counter exam ple is known and it has been conjectured that such a counter example m ust be hundreds of digits long. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 49 "Here is a test of a Fermat prime using \"isprime\":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 143 "n:=1;\nm:=2^n;\nf ermat:=2^m+1;\n\n# True or False: 2^(2^n) + 1 is prime.\nisprime(ferma t);\n\n# What are the factors of 2^(2^n) + 1 ?\nifactor(fermat);" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 59 "Euclid's proo f that there are an infinite number of primes:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "# Is the nu mber formed in the proof prime?\n# Try it for some different primes.\n \nW:=(2*3*5+1);\nisprime(W);\nifactor(W);" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 256 89 "Euclid's proof that there are \+ an infinite number of primes with the last prime p = 191:\n\n" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 339 "# By trial and error, find \+ how many primes are greater than 5 and less than or equal to 191. The \+ answer is 40.\n# The upper limit 41 on the loop below is always set to be one more.\n\nprod:=2*3*5:\np:=5:\nfor i from 1 while i < 41 do\n \+ np:=nextprime(p);\n prod := prod * np;\n p:=np;\nend do:\nTheLast Prime:=np;\nprod;\nW:=prod + 1;\nisprime(W);\n" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 116 "We can also calculate the Greatest Common Divisor of two numbers; and the next prime and previous prime of a number:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 101 "g cd(89,144);\nisprime(191);\nprevprime(191);\nnextprime(89);\nithprime( 43); #gives ith prime number\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "?isprime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "?nextprime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "?prevprime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "?loop" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "20 0 0" 194 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }