Briques élémentaires des entiers, les nombres premiers irriguent tous les domaines des mathématiques. Mais 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 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 à Terence Tao, en passant par les travaux de Mersenne, Fermat, Gauss et par l'hypothèse de Riemann, "graal" des mathématiques.