Discussion :

[Astraya]

Bonjour,

Je viens vous demander un peu d'aider concernant la compréhension d'un algorithme fonctionnel. Mais je ne comprend pas certaines parties, ce n'est pas le code mon problème mais les mathématiques qui sont derrières tout ça.
C'est un test de primarité que j'ai récupérer dans un algorithme de génération de nombre primaire avec AKS en C++.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool IsPrime(unsigned int nbr)
{
    //2 est le seul entier pair premier
    if(nbr == 2) 
        return true;
    //Tous les nombres inférieurs à 2 et pair ne sont pas premier
    if(nbr < 2 || isEven(nbr)) 
        return false;
 
    const unsigned int iMax = sqrt((float)nbr) + 1;
    unsigned int i;
    for (i = 3; i <= iMax; i += 2)
    {
        if (nbr % i == 0)
            return false;
    }
    return true;
}

Voila, je ne comprend pas à partir de la racine carré puis ensuite, la boucle...

Quelqu'un pourrait me renseigner?

Merci beaucoup par avance.

[Jean Dumoncel]

Bonjour,

Suppose que tu trouves un nombre b qui divise ton nombre N et qui soit supérieur à sqrt(N)+1. Alors N = b*c. Que peux-tu dire sur c?

[Astraya]

La j'en ai aucune idée.
Je ne comprend pas pourquoi sqrt(N)+1? Qu'est que ça donne de spécial? la racine carrée de ce nombre +1?
ça me donne un multiple de mon nombre mais vu qu'il est impaire, il seras tronqué car mis dans un entier. et pourquoi + 1? ça pour moi c'est un peu comme chercher à résoudre l'équation du tout que Einstein cherchais...
Je ne vois pas , je pourrais le voir si je comprend ce qu'est la racine carrée d'un nombre impaire + 1.

[Jean Dumoncel]

En fait il faut prendre comme limite sqrt(N) et non sqrt(N)+1. (le test sur sqrt(N)+1 est inutile).

Je cite l'explication wikipédia :

si N = pq alors soit p≤sqrt(N) soit q≤sqrt(N)

Donc l'un au moins des 2 diviseurs est inférieur à sqrt(N), donc si tu trouves un diviseur plus grand que sqrt(N), cela veut dire qu'il existe un autre diviseur inférieur à sqrt(N) or tu es censé avoir déjà testé les entiers inférieurs à sqrt(N).

[Astraya]

Ah! très bien! Merci énormément pour tes lumières magelan!
Donc ce qu'il fait, c'est tester tout les diviseurs plus petit que sqrt(N).
En testant tout les nombres inférieurs à cette valeur, il sera en mesure de savoir si la relation est vrai? Si jamais il ne trouve pas de diviseur plus petit, cela voudrais dire que aucune des deux conditions suivantes n'est possible et que donc N n'as pas de diviseur possible, autre que 1 et bien sur lui même c'est ça?

Mais pourquoi incrémente-t-il de deux? Est ce parce que un nombre impair ne peut pas être divisé par un nombre pair sans avoir de reste? si simplement?

On vas y arrivé

[Jean Dumoncel]

Ah! très bien! Merci énormément pour tes lumières magelan!
Donc ce qu'il fait, c'est tester tout les diviseurs plus petit que sqrt(N).
En testant tout les nombres inférieurs à cette valeur, il sera en mesure de savoir si la relation est vrai? Si jamais il ne trouve pas de diviseur plus petit, cela voudrais dire que aucune des deux conditions suivantes n'est possible et que donc N n'as pas de diviseur possible, autre que 1 et bien sur lui même c'est ça?

Mais pourquoi incrémente-t-il de deux? Est ce parce que un nombre impair ne peut pas être divisé par un nombre pair sans avoir de reste? si simplement?

Oui et oui. Aucun nombre impaire (dans l'ensemble des entiers naturels) ne peut être divisé par un nombre pair.

[Astraya]

OK très bien merci beaucoup.
Une dernière question cependant, il s'agit bien ici du test de primarité AKS? et non pas un autre? Merci

[Invité]

Bonjour,
Je suis ce sujet depuis le début, mais maintenant j'ai un doute.
D'après le contexte, pour "test de primarité AKS", j'avais traduit "test de nombre premier".
Mais maintenent, je n'en suis plus sûr.
La définition d'un nombre premier est qu'il n'est divisible que par 1 et par lui-même, dans l'ensemble des nombres entiers.
Ce qui justifie que à part 2 qui est entier et pair, aucun autre nombre pair de peut être un entier. Ensuite, la limitation de la recherche se fait à sqrt(N) parce que le diviseur éventuel de N ne peut pas être plus grand que la racine carrée de N, comme il a été expliqué.
Donc, ma question, quelle est la définition de la primarité AKS.

[Astraya]

Bonjour,
Voila la documentation officiel rendu par les 3 indiens sur leurs travaux :
http://www.cse.iitk.ac.in/users/mani...y_original.pdf
page 4, il y a l'algorithme qui ressemble à ce que j'ai donné mais je ne suis pas sur de ça parfaite reproduction.

[Invité]

Je ne vois très bien le rapport.
Je n'ai pas tout lu, mais apparemment il s'agit bien de trouver si un nombre est premier ou pas, mais je ne pense pas que votre code soit une traduction de l'algorithme décrit dans l'article.

L'algorithme type boucle jusqu'à la limite de la racine carré, celui-ci est beaucoup plus sioux.

[Jean Dumoncel]

Je confirme, ce n'est pas la méthode AKS, je n'avais pas vraiment fait attention au fait que tu voulais la méthode AKS.

La méthode de ton algo est une méthode naïve : en gros tu tests toutes les divisions possibles (en excluant d'office les nombres paires et les nombres supérieure à sqrt(N)). Donc c'est une méthode très lourde dès que les nombres sont un peu grand.