T-99 : Quatre Vingt Dix Neuf Problèmes en Tcl - Arithmétique

 

T-99 : Quatre Vingt Dix Neuf Problèmes en Tcl - Arithmétique

* P2.01 (**) Déterminer si un nombre entier est premier Réponse:

 proc isprime n {
  set max [expr {int(sqrt($n))}]
  set d 2
  while {$d <= $max} {
       if {$n%$d == 0} {return 0}
       incr d
  }
  return 1
 }

 isprime 7

ou

 proc isprime n {expr {$n>1 && ![regexp {^(oo+?)\1+$} [string repeat o $n]]}}

 isprime 7

ou

 package require math::numtheory
 ::math::numtheory::isprime 7

 isprime 7

* P2.02 (**) Trouver le plus grand commun diviseur de deux nombres entiers positifs Réponse:

 proc gcd {p q} {
  if {$q == 0} {return $p}
  gcd $q [expr {$p % $q}]
 }

 gcd 36 63

* P2.03 (*) Déterminer si deux nombres entiers positifs sont premiers entre eux Réponse:

 proc coprime {p q} {gcd $p $q}

 coprime 35 64

* P2.04 (**) Calculer l'indicatrice d'Euler (fonction Phi d'Euler) Réponse:

 proc totient_phi n {
  for {set i 1} {$i <= $n} {incr i} {if {[gcd $i $n] == 1} {incr j}}
  set j
 }

 totient_phi 10

* P2.05 (**) Déterminer les facteurs premiers d'un entier positif Réponse:

 proc prime_factors n {
  set res {}
  for {set i 2} {$i <= $n} {incr i} {
     while {$n%$i == 0} {
          set n [expr {$n/$i}]
          lappend res $i
     }
  }
  set res
 }

 prime_factors 315

* P2.06 (**) Déterminer les facteurs premiers d'un entier positif avec liste de multiplicité Réponse:

 proc prime_factors_mult n {
  set res {}
  foreach i [encode [prime_factors $n]] {
     if {[llength $i]==1} then {lappend res [list $i 1]} else {lappend res [lreverse $i]}
  }
  set res
 }

 prime_factors_mult 315

* P2.09 (*) Calculer la liste des nombres premiers compris entre deux entiers Réponse:

 proc even n {expr {($n % 2) == 0}}

 proc prime n {
  set res [list 2]
  for {set i 3} {$i <= $n} {incr i 2} {
     set max [expr {int(sqrt($i))}]
     foreach j $res {
            if {$j  > $max} {
              lappend res $i
              break
            }
            if {![expr {$i % $j}]} {break}
     }
  }
  set res
 }

 proc primerange {p n} {
  if [even $p] {incr p}
  set res {}
  foreach i [prime $n] {if {$i >= $p} {lappend res $i}}
  set res
 }

 prime_range 10 30

* P2.10 (**) Conjecture de Goldbach Réponse:

 proc goldbach n {
  if {$n % 2 == 0} then {
    set l {}
    for {set i 2} {$i <= [expr {$n/2}]} {incr i} {
       set j [expr {$n - $i}]
       if {[isprime $i] && [isprime $j]} then {
         set l [list $i $j]
         break
       }
    }
    return $l
  }
 }

 goldbach 28

* P2.11 (**) Une liste de pairs de Goldbach compris entre deux entiers Réponse:

 proc goldbach_list {m n} {
  if {$m % 2 != 0} {incr m}
  if {$n % 2 != 0} {incr n}
  set l {}
  for {set i $m} {$i <= $n} {incr i 2} {
     lappend l [list $i [goldbach $i]]
  }
  return $l
 }

 goldbach_list 9 20

et

 proc goldbach_limit {m n p} {
  if {$m % 2 != 0} {incr m}
  if {$n % 2 != 0} {incr n}
  set l {}
  for {set i $m} {$i <= $n} {incr i 2} {
     set g [goldbach $i]
     if {[lindex $g 0] >= $p && [lindex $g 1] >= $p} then {lappend l [list $i $g]}
  }
  return $l
 }

 goldbach_limit 2 2000 50

T-99 : Quatre Vingt Dix Neuf Problèmes en Tcl