Bonsoir,
ton algorithme est faux.

On peut, par exemple, l'essayer avec N=6 d'où D=6
au début de la boucle «tant que» on a T=3 et donc T²=9
9>6 :la boucle n'est pas effectuée
on a bien N=D
on affiche 6 est premier

Sinon, après corrections, il est vraisemblablement en O(n)

Dans le pire des cas, le nombre N saisi est premier.
Dans ce cas, la partie décimale de N/T n'est jamais nulle et on ne trouve pas d'autre diviseur que N.
L'algorithme s'arrête alors une fois que le compteur T a atteint racine carré de N.
Comme T est incrémenté de 2 en 2, la complexité est au pire de racine carrée de N, sur 2.

Oui, verdurin je sais qu'il ne fonctionne pas pour n=6, et pour beaucoup d'entier pair, mais pour savoir que 6 est composé, je pense que je n'ai pas besoin de cet algorithme, et de même pour les entiers pairs.

Merci pour vos réponses, c'est aussi ce que j'avais trouvé comme complexité, mais ne trouvez-vous pas cela un peu étrange, je veux dire par là n'est-ce pas un peu utopique qu'un algorithme de factorisation fonctionne en O(N) ?

Qu'entends-tu par utopique ?
Si N est premier, T augmente de 2 en 2 jusqu'à racine de N.
Où est l'utopie la dedans ?

Ce que je veux dire c'est que l'on peut lire sur wikipédia par exemple que de puissant algorithme fonctionne en un temps polynomial, le meilleur d'entre eux fonctionnerait en O(n⁶).

Je pense que tu fais une confusion sur la nature de ces algorithmes.

Je ne sais pas, je me base par exemple sur ce type d'algorithme : http://fr.wikipedia.org/wiki/Test_de_primalité_AKS

Ou sur la définitionde 'n' : peut-être le nombre de chiffres de N et non N lui même ?

Oui, c'est bien ça : la complexité est polynomiale en n = Log(N).
Cela revient à dire que l'algorithme est polynomiale par rapport au nombre de chiffres de N.

D'accord je comprends d'où vient mon erreur. Merci de m'avoir aidé à comprendre