isPrime(n) avec une regex

Ce minuscule script Perl d'une seule instruction ( print str =~ regex ? no : yes ) indique par YES ou NO si le l'entier passé en argument sur la ligne de commande est un nombre premier :

#!/usr/bin/perl
#usage: isPrime.pl <entier>
print (('@' x $ARGV[0]) =~ /^.?$|^(..+?)\1+$/ ? "NO\n" : "YES\n");

Spirale d'Ulam

Le cœur du script est une expression régulière qui matche quand l'argument n'est pas un nombre premier. Cette expression régulière s'applique à une chaîne de caractères identiques et de longueur égale à la valeur de l'argument. 

La chaîne contenant autant de @ qu'indiqué par l'argument est construite avec  ('@' x $ARGV[0]).

Exemple: isPrime.pl 6  travaille sur la chaîne "@@@@@@"

La première partie de la regex ^.?$ détermine s'il y a 0 ou 1 caractère dans la chaîne, autrement dit si le nombre à tester est 0 ou 1. Si c'est le cas le nombre n'est pas premier (affiche NO).

La deuxième partie de la regex ^(..+?)\1+$ détermine s'il est possible de décomposer la chaîne en la répétition d'une sous chaîne d'au moins 2 caractères. Si c'est le cas c'est que la longueur de la chaîne (donc la valeur de l'argument) peut s’écrire L * N, (avec L>0 et N>1) et donc le nombre n'est pas premier (affiche NO).

• L est la longueur de (..+?)
  
• n est le valeur que représente le + dans \1+

Exemples :

• isPrime.pl 9
  La chaîne de 9 caractères "@@@@@@@@@" est décomposée en 3 répétitions de "@@@"
  ==> matche ==> 9 n'est pas un nombre premier.
  
  
• isPrime.pl 12
  La chaîne de 12 caractères "@@@@@@@@@@@@" est décomposée en 6 répétitions de "@@"
  ==> matche ==> 12 n'est pas un nombre premier.
  
  
• isPrime.pl 11
  La chaîne de 11 caractères "@@@@@@@@@@@" n'est pas décomposable en N répétitions d'une chaîne de longueur L
  ==> ne matche ==> 11 est un nombre premier.

La classique boucle de cherche les diviseurs d'un nombre est prise en charge par la recherche itérative d'une solution dans le moteur d'expressions régulières. Bien sur la méthode n'est ni efficace en place mémoire ni en temps de calcul, mais elle est originale.

Vous trouverez une liste des 50000 premiers nombres premiers ici.

Note: L'image utilisée pour illustrer ce post est la spirale d'Ulam qui représente la position des nombres premiers sur une spirale. Les lignes droites semblent indiquer une certaine organisation (un pattern) des nombres premiers...intriguant...

Histoire de TAoCP

Si vous faites partie de la génération de développeurs qui ont appris à programmer dans des livres, vous connaissez sûrement ces bouquins écrits pour surfer sur une mode, pour essayer de se faire un nom. Des livres impersonnels, avec de la forme mais pas de fond. PHP disparaît des radars et avec lui une charrette d’auteurs insipides.

A l’opposé de ces livres de circonstance je vous présente : « The Art of Computer Programming » (TAoCP) de Donald Knuth, Professeur à Standford. Un ouvrage rédigé par un seul auteur sur toute une vie, sur un seul sujet : l’Algorithmique. La conception de l’ouvrage n’a pas été linaire, loin de là, et comme tout projet il a subit d’énormes retards et changements de direction.

Notes : Vous connaissez l’histoire de Git ? Et bien c’est un peu la même chose qui s’est passé pendant la rédaction/édition de The Art of Computer Programming  (TAoCP). En 1973, à l’occasion de la seconde édition du volume 2,  Knuth était insatisfait des systèmes de composition de page de l’époque. Il décide de faire une pause (de 1974 à 1996 !) pour concevoir l’outil qui lui convient pour rédiger son ouvrage (Tout comme Linus Torval écrit Git pour gérer le code du kernel Linux). Le résultat est metafont et TeX qui sont toujours utilisés en 2025 au travers de LaTeX et TeX Live

Pour convaincre ceux qui hésiteraient à se lancer dans l’achat (et la lecture) de cette œuvre je ne ferais pas mieux que ce post "Dix bonnes raisons de lire ou relire The Art of Computer Programming".

Dans sa forme actuelle (déc 2024) TAoCP est constitué de 5 volumes + un fascicule :

Volume 1: Fundamental Algorithms (1968, 3éme Édition 1997)
Volume 2: Seminumerical Algorithms (1969, 3éme Édition 1997)
Volume 3: Sorting and Searching (1973, 2éme Édition 1998)
Volume 4A: Combinatorial Algorithms, Part 1 (2011)
Volume 4B: Combinatorial Algorithms, Part 2 (2023)
+
Fascicule 7, Constraint Satisfaction (2025)  pour un futur volume 4C ?...

Les Volume 4A et 4B ont d’abord été publié (dans le désordre) sous forme de fascicules:

• Fascicule 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
  Fascicule 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
  Fascicule 2, Generating All Tuples and Permutations (2005),
  Fascicule 3, Generating All Combinations and Partitions (2005)
  Fascicule 4, Generating All Trees; History of Combinatorial Generation (2006)
  Ces cinq premiers fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4A - Combinatorial Algorithms Part 1"en 2011

• Fascicule 5, Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links (2019)
  Fascicule 6, Satisfiability (2015)
  Ces deux fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4B - Combinatorial Algorithms Part 2" en 2023.

En prévision :

Volume 5: Syntactic algorithm,
Volume 6: The Theory of context-free languages
Volume 7: Compiler techniques

Ce dernier volume sur les compilateurs est en fait la raison initiale de tout ce travail. En effet, en 1962 Knuth travaillait sur des compilateurs Algol et Fortran et avait entamé l’écriture d’un livre sur ce sujet, mais il avait jugé qu’il fallait d’abord introduire des concepts fondamentaux  … Introduction qui a donné les 5 volumes actuels !

Les exemples ne sont pas écrits en C, ni Pascal, ni C++, ni Java, ni Rust. Mais avec MIX pour les 3 premiers volumes puis avec MMIX. C'est le langage d’une machine virtuelle avec une architecture RISC (ben oui, en 1968 on savait déjà ce qu’était une VM) 

 

 

Le cordonnier, l’informaticien et l’Opinel

Logo Opinel

J’ai été élevé par mes grands-parents, à Albi, pendant les années 60. Mon grand-père, mineur, électricien et grand bricoleur devant l’éternel, avait toujours son Opinel dans la poche. Il faisait tout avec. Il coupait le pain, la viande, bricolait, curait sa pipe, vidait le poulet, taillait des bâtons pour faire des moulins à eau. La liste est sans fin.

Le dimanche nous allions au marché sur la place de l’imposante cathédrale St Cécile. A cette époque les centres commerciaux et leurs galeries commerciales, avec le cordonnier qui fait des clefs, n’existaient pas. Certains artisans faisaient encore du porte à porte comme le rémouleur ou le rempailleur mais la plupart avaient une échoppe face à la cathédrale et autour des halles. Un jour que nous portions des chaussures à réparer au cordonnier (à cette époque on ne jetait pas), avant d’entrer dans la boutique, mon grand-père me dit en montant le cordonnier juste derrière la vitre en train de travailler un morceau de cuir :

-    Regarde, avec le dos de la lame de son Opinel il marque le cuir qui lui permet de gagner son pain et avec l’autre côté il coupe le pain ainsi gagné.

Pour moi qui n’avais pas encore dix ans c’était magique : On pouvait vivre avec un seul outil ! Je comprenais mieux pourquoi l’Opinel dans la poche de mon grand-père était si précieux.

Étonnamment, j’ai passé ma vie avec un seul outil entre mes mains: l’ordinateur. Même si l’écart technologique entre l’Opinel et l’ordinateur est immense, ils ont en commun d’être d’un usage universel, et depuis une décennie les ordinateurs rentrent aussi dans une poche. Mais il y a deux différences abyssales entre ces deux outils qui résument bien des choses : 

• Mon grand-père (1901 - 1992) a dû avoir trois ou quatre Opinel dans sa vie.
  Moi, depuis 1977, j’ai changé d’ordinateur tous les trois ou quatre ans. 
• Je peux prendre l’avion avec mon Smartphone dans la poche mais pas avec mon Opinel.
  

Comment bloquer le démarchage téléphonique ?

Depuis septembre 2022 le démarchage téléphonique doit se faire depuis des numéros spécifiques, donc identifiables. Les numéros commençant avec les préfixes ci-dessous sont maintenant les seuls autorisés à faire du démarchage téléphonique en France Métropolitaine :

01.62.xxxxxx   01.63.xxxxxx
02.70.xxxxxx   02.71.xxxxxx
03.77.xxxxxx   03.78.xxxxxx
04.24.xxxxxx   04.25.xxxxxx
05.68.xxxxxx   05.69.xxxxxx
09.48.xxxxxx   09.49.xxxxxx 

Chacun de ces blocs représente tout de même un million (1,000,000) de numéros !

Pour le démarchage téléphonique dans les Départements et Régions d’Outre-Mer (DROM) il y a cinq préfixes autorisés :

09.47.5x.xxxx
09.47.6x.xxxx
09.47.7x.xxxx
09.47.8x.xxxx
09.47.9x.xxxx

Ici chaque bloc représente cent milles (100,000) numéros.

Au total, 12 millions cinq cent milles (12,500,00) numéros sont officiellement réservés au démarchage téléphonique en France !!

Ces 17 préfixes font partie du "plan nationale de numérotation" définit par l'ARCEP [pdf] (chapitre 2.3.7 Conditions spécifiques aux numéros polyvalents vérifiés). Pour bien comprendre ce qui est, ou n'est pas, autorisé, lire cette liste de FAQ de l'ARCEP destinée aux professionnels du démarchage téléphonique.

Android permet de bloquer des numéros qui vous ont déjà appelé, mais on ne peut pas bloquer préventivement. De toute façon il n’est pas question de bloquer manuellement plus de 12 millions de numéros.

L’application Android SpamBlocker (open source et gratuite) permet de faire du blocage préventif, numéros par numéros, mais aussi sur la base de modèles. Par exemple tous les numéros se terminant par 123 ou tous les numéros commençant par 0948 ou 33948 ou tous les numéros contenant 666…

En informatique ce système de modèle (commençant par, terminant par, incluant …) s’appelle les ‘expressions régulières’. Quand on ne connaît pas c’est incompréhensible, et c’est parfois complexe, même quand on connaît bien.

Si vous voulez utiliser l’application SpamBlocker voici les deux expressions régulières à utiliser.

Expression régulière pour bloquer les numéros autorisés à faire du démarchage téléphonique en France métropolitaine :

^(?:33|0)?(?:162|163|270|271|377|378|424|425|568|569|948|949)\d{6}$

Expression régulière pour bloquer les numéros autorisés à faire du démarchage téléphonique en France d’outre-mer (DROM):

^(?:33|0)?(?:9475|9476|9477|9478|9479)\d{5}$

==> Ces expressions régulières ne doivent pas contenir d'espaces.

Exemple:

Notes:

• Avant d’appliquer les expressions régulières SpamBlocker supprime les zéros de tête des numéros entrant. Les expressions présentées ici ne tiennent pas compte de cette simplification et sont donc utilisables dans d'autres applications.
  
  
• SpamBlocker contient un système pour simuler des appels entrants et ainsi tester les expressions régulières et autres règles (SpamBlocker propose d'autres méthodes de blocage). Exemple de tests confirmant que ce numéro sera bloqué par l'expression régulière nommée 'pub' qu'il soit préfixé par +33 ou pas:
  
  
  
  
  
  Quand on fait ces tests vérifier que ça bloque les numéros voulus, mais pas les autres...
  

Il existe d'autres applications comme SpamBlocker mais ce dernier présente un ensemble d'avantages unique:

• open source (code et support via GitHub)
  
• gratuit
• pas d'annonces dans l'appli (c'est un minimum pour une appli anti spam !)
  
• pas d'achat via l'appli
• pas de liste de numéros bloqués/autorisés par défaut (toujours source de doutes. Rappelez vous les compromissions de AdBlock...)
• gestion des appels et des sms entrants.
  
• et le plus important: pas d’accès réseau (donc pas de fuites de données)

Disponible sur F-Droid et sur GitHub

Comment ne pas ce faire avoir par les démarcheurs !

L’idéal est de ne jamais répondre à un numéro masqué ou inconnu. Si l'appel est important l'appelant laissera un message sur votre messagerie.

Si vous rappelez la personne soyez très vigilant sur le numéro que vous rappelez. Il se pourrait que ce soit un numéro surtaxé, ou à l’étranger. Plutôt que de rappeler vous pouvez envoyer un SMS. Là aussi attention au numéro.

Si malgré tout vous répondez à un appel d'un numéro masqué ou inconnu:

• Ne parlez jamais, absolument jamais,  en premier (ça donne votre sexe, votre age approximatif et éventuellement votre ethnie ou nationalité).
  
• Si personne ne parle dans les 10 secondes raccrochez.
• Si elle ne l'a pas fait, exigez que la personne se présente clairement avant de poursuivre la conversation.
• Ne soyez pas crédule.
  
• Ne donnez strictement aucune information, pas même le nom de votre chat.
• Si le contenu de la conversation ne vous convient pas dites courtoisement
• que vous n’êtes pas intéressé,
• que vous allez raccrocher,
• que vous ne voulez plus être appelé.
• raccrochez rapidement sans plus de justification.
• Si vous donnez suite à un appel commercial ne le faites que par écrit via une adresse e-mail secondaire (surtout pas celle que vous utilisez avec votre banque ou l'administration).
  

Enfin, si vous êtes harcelé par des démarcheurs

• ajouter un à un ces numéros à votre bloqueur.
• s'inscrire et se plaindre sur BlocTel: https://www.bloctel.gouv.fr/ (meme si l'effet est loin d'être évident...)