Nombre premier ou pas?

Bonjour,
Je vous propose un petit exercice pour les plus expérimentés (en fait, on peut le faire très facilement) : Dire si un nombre est premier ou pas.
Difficulté: /
Exercice: Votre mission, si vous l'acceptez, sera de créer une fonction qui va indiquer si un nombre est premier ou pas.
Éléments:
Petit rappel : un nombre premier est un nombre qui n'est divisible que par 1 et par lui-même.
Ensuite (facultatif) : si un nombre n'est divisible par aucun des nombres inférieurs à sa racine carré, il est premier. En gros, si tous les nombres inférieurs à la racine carré du nombre à testé ne sont pas des diviseurs du nombre à testé alors, le nombre à testé est premier.
La fonction prendra comme seul paramètre le nombre à tester.
Elle devra renvoyer true si le nombre est premier, false dans le cas contraire.

Si vous avez besoin de plus d'aide, n'hésitez pas à me le dire.

Je vais essayer (décidemment j'essaye plein de truc hihi ^^)
Un peu dur quand même

Puis-ce que personne ne semble comprendre la simplicité de la fonction à créer, voici ma version :

Code:

<?php
function is_prime($n)
{
  $sqrt = sqrt($n);
  for($i=3;$i<=$sqrt;$i+=2)
  {
      if($n%$i==0)
        return false;
  }
  return true;
}
?>


Voilà, c'était si difficile que ça?

pas assez rapide ton code
j'ai une version en C que je vais traduire en PHP

pas assez rapide?
Oui, en effet, on pourrait aussi éviter les multiples de 3 et de 5 dans la boucle en elle-même...
Mais normalement, on doit pas pouvoir faire beaucoup plus rapide en PHP. Si ton code l'est plus, c'est tout simplement que c'est du C et qu'il est déjà compilé et l'ordinateur le comprend facilement, contrairement au code PHP qui doit être "traduit" avant d'être exécuté.

Bon, j'ai testé et il restait quelques erreurs .
Voici donc une version qui marche :

Code:

<?php
function is_prime($n)
{
  if($n<=2 OR $n%2==0 OR ($n%3==0 AND $n!=3) OR ($n%5==0 AND $n!=5))
    return false;
  $sqrt = sqrt($n);
  for($i=3;$i<=$sqrt;$i+=2)
  {
      if($n%$i==0)
        return false;
  }
  return true;
}
?>

Avec une boucle for qui appelle la fonction, j'arrive à avoir la liste des nombres premiers inférieurs à 100000 en légèrement plus qu'une seconde (temps de transfert compris).

au niveau du teste c'est ce que je fait, mais tu peut aussi tester les multiple de 7, pour etre un chouya plus rapide ^^
sinon mon code est identique, faut dire il y a pas 36 solution xD


effectivement le C est plus rapide

Par contre, il faut que je réduise la boucle en ne bouclant que sur les nombres qui ne sont pas multiples de 2, 3 et 5, car pour les grands nombre, ça prend plus de temps