Primes are positive integers that can only be divided (without remainder) by 1 and themselves. Examples from [RS]'s collection: 1234567891 987654321987654329 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. " ---- [Category Concept] | [Arts and crafts of Tcl-Tk programming]