Voir la source de Project Euler

{{Langue du titre|en}}
{{Infobox Site web
 | nom          = http://projecteuler.net
 | logo         = Leonhard Euler.jpg
 | légende      = {{Langue|en|Project Euler}}.
 | image        = 
 | commercial   = Non
 | description  = 
 | publicité    = 
 | taille logo  = 125
 | url          = [http://projecteuler.net/ projecteuler.net]
 | type         = Résolution de problèmes mathématiques et algorithmiques
 | langue       = [[Anglais]]
 | inscription  = Gratuite
 | propriétaire = 
 | auteur       = Colin Hughes, alias euler
 | lancement    = {{date|5|octobre|2001|en informatique}}
 | revenus      = 
 | état actuel  =
 | slogan       = 
 | siege social = 
}}

'''{{Langue|en|Project Euler}}''' est un [[site web]] proposant une série de problèmes [[mathématiques]] conçus pour être résolus à l'aide de [[programme informatique|programmes informatiques]]. Le but du projet est d'attirer des adultes et des élèves intéressés par les mathématiques et l’[[informatique]]. Il comprend actuellement plus de 850 problèmes<ref group="Note">854 problèmes au 12 septembre 2023.</ref>{{,}}<ref>{{Lien web|langue=en|titre=Project Euler - Problems|url=http://projecteuler.net/show=all|site=projecteuler.net|date=|consulté le=17 juin 2017}}.</ref> de difficultés variables, chacun pouvant être résolu en principe en moins d'une minute par un [[algorithme]] efficace sur un [[ordinateur]] de puissance modeste. De nouveaux problèmes sont progressivement ajoutés, actuellement au rythme d'un toutes les deux semaines, depuis la création du site en [[2001]]. Un forum spécifique à chaque problème est accessible aux utilisateurs qui l'ont résolu. Une section Scores classe également les membres selon le nombre de problèmes résolus. Il existe quatorze niveaux de classement selon le nombre de problèmes résolus, ainsi qu'un classement spécial basé sur la vitesse de résolution des derniers problèmes parus.

Depuis la création du site en 2001, plus de {{unité|1000000|utilisateurs}} se sont enregistrés sur le site<ref name="stats">{{Lien web|langue=en|url=http://projecteuler.net/statistics|titre=Project Euler - Statistics|site=projecteuler.net|consulté le=19 septembre 2012}}.</ref>.

== Exemple de problème et solutions ==
Une traduction du premier problème est<ref group="Note">L'énoncé original est {{citation étrangère|langue=en|If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.}}</ref> :

{{Citation bloc|Si on liste tous les entiers naturels inférieurs à 10 qui sont multiples de 3 ou de 5, on obtient 3, 5, 6 et 9. La somme de ces nombres est 23. Trouvez la somme de tous les multiples de 3 ou de 5 inférieurs à {{formatnum:1000}}<ref group="Note">C'est le [[Fonction OU|OU inclusif]] qui est utilisé ici.</ref>.}}
Bien que ce problème soit l'un des plus simples du site, il permet d'illustrer le gain de temps potentiel d'un algorithme efficace<ref group="Note">En informatique, quand un algorithme répond correctement au problème posé, on cherche souvent à l{{'}}''optimiser''. On veut que l'algorithme utilise le moins de temps et de [[Allocation de mémoire|mémoire]] possible. Voir [[Théorie de la complexité des algorithmes|ici]] pour plus de précisions.</ref> par rapport à un algorithme naïf. L'algorithme ''[[recherche exhaustive|brute-force]]'' examine chaque entier naturel inférieur à {{formatnum:1000}} et actualise la somme de ceux qui remplissent les critères. Cette méthode est facile à implémenter ; en [[pseudo-code]], cela peut s'écrire :

<pre>
initialiser SOMME à 0;
  pour n variant de 1 à 999 faire
    si n est un multiple de 3 ou de 5 alors // Autrement dit si n est divisible par 3 ou par 5
      ajouter n à SOMME;
  fait;
renvoyer SOMME
</pre>

Cependant, pour les problèmes plus complexes, trouver un algorithme efficace devient indispensable. Pour cet exemple, nous pouvons réduire {{Unité|1000|opérations}} à quelques-unes en utilisant le [[principe d'inclusion-exclusion]] et une formule de [[somme (arithmétique)|sommation]] :

: <math display="inline">\mathrm{sum}_{\text{3 ou 5}}(n+1) = \mathrm{sum}_3(n+1)+\mathrm{sum}_5(n+1)-\mathrm{sum}_{15}(n+1)</math>
: <math>= \frac{3}{2} \left(\left\lfloor \frac{n}{3} \right\rfloor \left(\left\lfloor \frac{n}{3} \right\rfloor + 1\right) \right) + \frac{5}{2} \left(\left\lfloor \frac{n}{5} \right\rfloor \left(\left\lfloor \frac{n}{5} \right\rfloor + 1\right) \right) - \frac{15}{2} \left(\left\lfloor \frac{n}{15} \right\rfloor \left(\left\lfloor \frac{n}{15} \right\rfloor + 1\right) \right)</math>
: <math>= \sum_{i=1}^{\lfloor \frac{n}{3} \rfloor} 3i + \sum_{i=1}^{\lfloor \frac{n}{5} \rfloor} 5i - \sum_{i=1}^{\lfloor \frac{n}{15} \rfloor} 15i</math>

Où <math>\mathrm{sum}_k(n+1)</math> désigne la somme des multiples de <math>k</math> inférieurs à <math>n+1</math> et <math>\lfloor . \rfloor</math> désigne l'arrondi à l'entier inférieur.

Implémentation en [[Python (langage)|Python]] :
<syntaxhighlight lang="python" line="1">
def sum_1_to_n(n):
   return n * (n + 1) / 2

def sum_multiples(limit, a):
   return sum_1_to_n((limit - 1) // a) * a

sum_multiples(1000, 3) + sum_multiples(1000, 5) - sum_multiples(1000, 15)
</syntaxhighlight>

Grâce à cet algorithme, la solution pour une borne supérieure à {{formatnum:10000000}} peut être obtenue presque aussi rapidement que pour {{formatnum:1000}}. En [[notation de Landau]], l'algorithme brute-force est en O(''n'') tandis que l'algorithme efficace est en O(1) (si on considère que le coût des opérations arithmétiques est constant).

== Traductions du Projet Euler ==
À ce jour, il existe différentes traductions du Projet Euler (classées par ordre alphabétique) :
{| class="wikitable"
!Langue
!Lien
|-
| colspan="2" |'''• A'''
|-
|Anglais (Langue officielle)
|https://projecteuler.net
|-
|Allemand
|http://projekteuler.de/
|-
| colspan="2" |'''• C'''
|-
|Chinois
|Website 1: https://pe-cn.github.io/
Website 2: http://pe.spiritzhang.com/
|-
|Coréen
|http://euler.synap.co.kr/
|-
| colspan="2" |'''• F'''
|-
|Français
|https://projet-euler.fr

<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler https://web.archive]<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler .o]<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler rg]<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler /web/20120310103855/h]<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler tt]<nowiki/>[https://web.archive.org/web/20120310103855/http://toprog.fr.nf/index.php?Page=Exercices&Section=Euler p://toprog.fr.nf/index.php?Page=Exercices&Section=Euler]
|-
| colspan="2" |'''• P'''
|-
|Persan
|https://marhale3.github.io/
|-
| colspan="2" |'''• R'''
|-
|Roumain
|http://projecteuler.radumurzea.net/
|-
|Russe
|http://euler.jakumo.org/
|}

== Liens externes ==
* {{site officiel|langue=en|url=http://projecteuler.net|titre=Site officiel du Projet Euler}}

== Notes et références ==
=== Notes ===
{{Références|groupe=Note}}

=== Références ===
{{Traduction/Référence|en|Project Euler|273176423}}
{{Références}}

{{Portail|informatique théorique|programmation informatique}}

[[Catégorie:Média consacré aux mathématiques]]
[[Catégorie:Algorithmique]]