L'algoritmo che stai cercando di implementare è talmente "nuovo" che era già noto ad Eratostene nel terzo secolo a.C.

Fai una bella ricerca sul tuo search engine preferito per "crivello di Eratostene": un'ottima occasione per imparare bene una tecnica algoritmica fondamentale, usata anche in centinaia di altre applicazioni analoghe. Il metodo naif delle divisioni successive è ovviamente il massimo dell'inefficienza.