Était-ce utile?

La solution

L'algorithme que vous suivez est appelé Fermat test de primalité. Cependant, il y a plusieurs problèmes avec votre explication:

  • Vous dites "confirmer que PGCD (a, p) est <1". Cela n'a pas de sens que le GCD ne sera jamais inférieur à un. Ce que vous pouvez vérifier que PGCD (a, p) == 1. Si ce n'est pas 1, alors p n'est pas premier. Cela peut détecter un nombre Carmichael, mais peut-être seulement une petite chance de le faire.

  • La façon dont le test est effectué, est que pour une certaine valeur de p, vous choisissez plusieurs valeurs aléatoires d'un et de vérifier si un ^ (p-1)% p == 1. Si l'un d'entre eux est pas 1, alors p n'est pas premier. Les valeurs plus d'un que vous choisissez, plus votre précision.

  • Vous ne pouvez certainement pas vérifier pour tous valeurs de x comme vous le dites - car il y a trop de vérifier

  • .
  • Il est un moyen rapide pour effectuer exponentiation modulaire, même pour une grande base et exposant. Voir Wikipedia article . Vous aurez toujours besoin d'une méthode pour effectuer la multiplication et modulo sur les grands entiers.

  • Le Sieve d'Eratosthène est seulement utile pour trouver des petits nombres premiers.

  • Ce test peut déterminer à tort que le nombre Carmichael sont premiers. D'autres algorithmes tels que Rabin-Miller n'ont pas ce problème.

Autres conseils

assez simple en C #. Je ne sais pas si ce serait plus rapide en termes de vitesse.

bool IsPrime(long n)
    {
        if (n == 1)
        {
            return false;
        }

        if (n < 4)
        {
            return true;
        }

        if ((n % 2) == 0)
        {
            return false;
        }

        if (n < 9)
        {
            return true;
        }

        if ((n % 3) == 0)
        {
            return false;
        }

        long r = (long)Math.Floor(Math.Sqrt(n));
        long f = 5;
        while (f <= r)
        {
            if ((n % f) == 0)
            {
                return false;
            }

            if ((n % (f + 2)) == 0)
            {
                return false;
            }

            f += 6;
        }

        return true;
    }

Il y a quelque temps j'ai écrit quelques fonctions en C # pour un usage personnel. J'espère que c'est bon pour vous

à long tmp public; public long [] = new tabnum longue [1];

priminum public void (longue NUM) {      Resto à long;      à long RISO;

 // 2 is only number pair prime
 tabnum[0] = 2;

 for (tmp = 3; tmp <= NUM; tmp++)
 {
     if ((tmp % 2) == 0) continue;// if num it's pair is not prime

     for (long Y = 0; Y < tmp; Y++)
     {
          riso = Math.DivRem(tabnum[Y], tmp, out Resto);
          if (Resto == 0) break;
          if(riso <= tabnum[Y]) 
          {
                 Array.Resize(ref tabnum, tabnum.Length + 1);
                 tabnum[tabnum.Length - 1] = tmp;
                 List1.Items.Add(tmp.ToString("###,###"));
                 break;
           } 
      }
  }

}

retour suivant vraie fonction si le nombre est premier

private bool IsPrimo (ulong tmpNum) {      ulong Y;

 if (tmpNum == 2) return true;

 if ((tmpNum % 2) == 0) return false;

 for (Y = 2; Y <= tmpNum; Y++)
 {
      if ((tmpNum % Y) == 0) break;
      if ((tmpNum / Y) <= Y) return true;
 }

 return false;

}

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top