Vérification de la primalité dans Forth

Question

Comment puis-je vérifier primality dans Forth?

Voici ce que je l'utilise maintenant, mais il obtient lent avec un plus grand nombre:

: prime (n - f) 
    DUP 2 < IF 
    DROP 0 EXIT 
    THEN 
    DUP 2 ?DO 
    DUP I I * < IF 
     DROP -1 LEAVE 
    THEN 
    DUP I MOD 0= IF 
     DROP 0 LEAVE 
    THEN 
    LOOP ; 

Answer 1

Une méthode probabiliste est simple avec le test Fermat, que vous pouvez consulter dans Wikipedia:

: *mod (a b n -- n2) 
    */mod drop ; 

: expmod { x e n -- n2 } \ compute x^e mod n by repeated squaring 
    e 0= if 1 exit 
    else 
     x e 2/ n recurse dup n *mod 
     e 1 and if x n *mod then 
    then ; 

: prime (n -- f) 
    3 swap dup expmod 3 = ; 

Si ce test indique que le nombre est composite, il est définitivement composite. S'il dit que le nombre est premier, alors il est PROBABLEMENT premier, mais quelques nombres composites vont glisser (ces nombres sont appelés "pseudoprimes"). Le test est assez rapide et suffisant à certaines fins.

Le code que vous avez testé teste les diviseurs 2,3,4,5, ... jusqu'à la racine carrée de n, et il serait environ 2x plus rapide s'il testait 2,3,5,7 ... puisqu'il n'est pas nécessaire de tester même les diviseurs supérieurs à 2.