\(\)Ένας τρόπος για να λύσετε την άσκηση ώστε να τρέχει στον χρόνο που απαιτείται είναι ανάλογος με το λεγόμενο κόσκινο του Ερατοσθένη.

Αυτός είναι ένας αλγόριθμος για να βρίσκουμε όλους τους πρώτους μέχρι το $N$ και δουλεύει ως εξής. Κάνουμε πρώτα την παρατήρηση ότι για να είναι ένας αριθμός πρώτος πρέπει να μη διαιρείται από κανένα μικρότερό του ακέραιο, ή, ακόμη καλύτερα, από κανένα μικρότερό του πρώτο αριθμό. Έπειτα φτιάχνουμε τη λίστα όλων των αριθμών από το 2 έως το $N$ και στην αρχή έχουμε 0 στη θέση κάθε ακεραίου. Ξεκινάμε μετά από την αρχή της λίστας και παίρνουμε τον πρώτο ακέραιο που βρίσκουμε που έχει 0 και σε όλα τα πολλαπλάσιά του (εκτός τον εαυτό του) βάζουμε 1, σηματοδοτώντας ότι δεν είναι πρώτος αριθμός. Έπειτα διαγράφουμε (μαρκάρουμε με 1) όλα τα πολλαπλάσια του επόμενου ακέραιου που έχει 0, κλπ. Στο τέλος ότι μείνει και έχει 0 είναι πρώτος.

Υπάρχει μια σχεδόν πλήρης αναλογία με τους squarefree ακεραίους: για να είναι ένας αριθμός squarefree πρέπει και αρκεί να μη διαιρείται με το τετράγωνο κανενός μικρότερου του ακεραίου. Ισοδύναμα, πρέπει και αρκεί να μη διαιρείται με το τετράγωνο κανενός μικρότερού του squarefree ακέραιου. (Ο αριθμός 1 δε θεωρείται squarefree.) Μπορεί άρα να λυθεί το πρόβλημα με ένα τελείως ανάλογο τρόπο με το κόσκινο του Ερατοσθένη όπου διαγράφουμε όχι τα πολλαπλάσια ενός αριθμού αλλά τα πολλαπλάσια του τετραγώνου του.