Για να ελέγξω αν ένας αριθμός, έστω Χ, είναι πρώτος, χρειάζομαι μια επανάληψη η οποία εξετάζει αν αυτός ο αριθμός έχει κάποιον διαιρέτη. Οπότε η επανάληψη που χρησιμοποιώ είναι
Για ι από 2 μέχρι χ div 2
Αν ο αριθμός είναι πρώτος τότε δεν θα υπάρχει κανένας διαιρέτης.
Το πρόβλημα είναι πως αν θέλω να βρω ποιοι αριθμοί στο διάστημα [1-500000], είναι πρώτοι, τότε βάζοντας ακόμη μια επανάληψη εξωτερικά ο χρόνος που απαιτείται για την εκτέλεση του αλγορίθμου, είναι τεράστιος. Δοκίμασα να απορρίψω αριθμούς οι οποίοι διαιρούνται με το 2, με το 3 με το 7 και με το 11 αλλά μάταια. Δεν έχει πέσει ο χρόνος εκτέλεσης.
Καμία ιδέα για μικρότερη πολυπλοκότητα;