Primes are positive integers >1 that can only be divided (without remainder) by 1 and themselves. Examples from RS's collection:
1234567891 987654321987654329 9223372036854775783
Two more primes, which my be algorithmically useful since they are close to pow(2,15) and pow(2,16):
32003 65521
Here's a very simple prime checker, which returns 1 for primes, else the first found divisor (and the quotient):
proc primetest n {
set max [expr wide(sqrt($n))]
if {$n%2==0} {return [list 2 [expr $n/2]]}
for {set i 3} {$i<=$max} {incr i 2} {
if {$n%$i==0} {return [list $i [expr $n/$i]]}
}
return 1
}AM commented in the Tcl chatroom: "The trick: divide by the first ten or twenty primes, after that: numbers of the form 6n+1 and 6n+5 may act as divisors. If you use only numbers of the form I mentioned, you gain about 50% with no loss of information."
This uses the first part of the proposal:
proc primetest2 n {
set max [expr int(sqrt($n))]
foreach i {
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181
191 193 197 199
} {
if {$i>=$max} break
if {$n%$i == 0} {return [list $i [expr $n/$i]]}
}
for {incr i 2} {$i<$max} {incr i 2} {
if {$n%$i == 0} {return [list $i [expr $n/$i]]}
}
return 1
} ;# RS
CL: A comment on prime calculations: for modest sizes--up to a few tens of decimal digits--I've always found it much the most satisfying to cache a list of known primes. I'm working in a stateful environment. My basic algorithm: test a trial number for quotients against my list of known primes, up to the square root of the trial number. Extend the list of primes, if it doesn't reach that high. It's a compact algorithm, it takes little space to keep the list, and I get excellent speed, especially for the frequent case where I want to know the primality of several different integers.
CL offers an example implementation [ugh: need to fix corrupted indentation]:
proc initialize_primes {} {
namespace eval primes {
variable list {}
proc is_prime candidate {
variable list
foreach prime $list {
# If a candidate has a factor, then
# it's composite.
if {![expr $candidate % $prime]} {
return false
}
# If a candidate has no prime factor
# smaller than or equal to its
# square root, then it has no prime
# factor, and therefore no factor,
# and therefore is itself prime.
if {[expr $prime * $prime > $candidate]} {
return true
}
}
# Use the list of primes we know to test the
# primality of the candidate. If the tests
# are inconclusive, extend the list, until
# the question is settled. In any case, be
# careful to maintain the list of known primes;
# this is valuable in consideration of new
# candidates.
while true {
set largest [get_next_prime]
if {[expr $largest * $largest >= $candidate]} {
return [is_prime $candidate]
}
}
}
proc get_next_prime {} {
variable list
if {{} == $list} {
set candidate 2
} else {
set candidate [lindex $list end]
while true {
incr candidate
if [is_prime $candidate] break
}
}
lappend list $candidate
return $candidate
}
}
}
initialize_primes
# Print the first thousand primes.
for {set i 1} {$i <= 1000} {incr i} {
puts [primes::get_next_prime]
} The first 6 million primes: http://www.geocities.com/ResearchTriangle/Thinktank/2434/prime/primenumbers.html
Mathworld: http://mathworld.wolfram.com/PrimeNumber.html "The largest known prime as of 2001 is the Mersenne prime 2**13466917 - 1. "
A prime tester on the Web at http://alpertron.com.ar/ecm.htm
Another useful prime-related concept is that of co-primality. Two numbers are co-prime if the greatest common divisor is 1.
Note that if P is a prime number, then for any Q, P and Q are co-prime.
RS wrote this cute recursive prime tester for breakfast fun:
proc prime i {prime0 $i [expr {int(sqrt($i))}]}
proc prime0 {i div} {
expr {!($i%$div)? 0: $div<=2? 1: [prime0 $i [incr div -1]]}
}DL wrote a Tcl script to let kids exeriment with Eratosthenes Sieve.
Category Concept | Arts and crafts of Tcl-Tk programming | Category Mathematics