Briques élémentaires des entiers, les nombres premiers irriguent tous les domaines des mathématiques. Mais qui les a inventés ? Quel est le plus grand nombre premier connu ? Un ordre caché gouverne-t-il leur distribution ? Et comment se répartissent-ils parmi les entiers (une question à 1 million de dollars) ? Pour percer ces mystères, les mathématiciens leur ont voué une guerre acharnée, quand ils ne se sont pas affrontés par travaux interposés. L'enjeu est aussi économique - saviez-vous que les nombres premiers s'achètent ? -, écologique - les calculs de primalité consomment une énergie colossale - et militaire - l'algorithme de cryptographie RSA à base de nombres premiers a été un temps interdit d'exportation par la NSA, l'Agence nationale de sécurité américaine. De coups tordus en batailles rangées, voici le récit de cette passionnante guerre souterraine, de l'Antiquité grecque jusqu'aux récentes contributions de Terence Tao, en passant par les travaux de Mersenne, Fermat, Euler, Gauss et par l'hypothèse de Riemann, "graal" des mathématiques.