L'unico modo che abbiamo per cercare un divisore di un numero intero N con le conoscenze attuali e quello di andare per tentativi cioè provare prima a dividere per 2 poi a dividere per 3 poi a dividere per 5 e così via. Quindi già si intuisce che è necessario utilizzare una struttura iterativa. Il problema è adesso vedere da quale valore deve partire l'indice controlla questa struttura iterativa e fino a quale valore deve arrivare. Il valore iniziale sarà indubbiamente 2; il valore finale...beh ci dobbiamo pensare un po'.
La prima risposta che di solito viene data è "arriviamo fino a N", poi è facile convincerci che effettivamente basterebbe arrivare fino alla metà di N (perché non esistono divisori di N che siano maggiori di N/2); ma possiamo fare ancora meglio. Infatti vale la seguente