من هم در مورد بهینه سازی برای اعداد اول یک چیزی اضافه کنم:

کافیه بر اعداد اول قبل از جذر خودش تست کنید که تقسیم نشه

اینجوری نعداد عملیات به شدت کاهش پیدا میکنه

مثلا برای اینکه بفهمیم 100 اول هست یانه:

جذر 100 میشه 10

اعداد اول قبل از 10 : 2 و 3 و 5 و 7

تعداد تقسیم ها = 4

حالا توی این مورد میبینیم بر 2 تقسیم میشه و عملیات رو پایان میدیم