Kommt darauf an, wie groß die Zahl ist.
Wenn du wissen willst, ob z. B. 1739 eine Primzahl ist, dann musst du versuchen, durch alle Primzahlen, die kleiner/gleich die Wurzel von 1739 sind, zu teilen (also durch 2, 3, 5, 7, ..., 41). Geht die Division auf (in unserem Fall ist das bei 37 der Fall), dann ist es keine Primzahl, sonst schon.
Mit Computerhilfe kann man aber auch bei viel größeren Zahlen feststellen, ob sie prim sind. Es gibt zum Beispiel einen probabilistischen Test, den Solovay-Strassen-Test, der blitzschnell auch bei einer 100-stelligen Zahl feststellen kann, ob sie (mit hoher Wahrscheinlichkeit) prim ist. Nach mehrmaligem Anwenden dieses Tests grenzt die hohe Wahrscheinlichkeit an Sicherheit.