Prologue Programme Pour Vérifier Si Un Nombre Est Premier

J'ai écrit le programme suivant basée sur la logique qu'un nombre premier n'est divisible que par 1 et lui-même. Je viens donc de passer par le processus de division à tous les nombres supérieurs à un an et moins de lui-même, mais je semble avoir un problème car j'ai tous les numéros saisis comme vrai. Voici mon code...

divisible(X,Y) :-
    Y < X,
    X mod Y is 0,
    Y1 is Y+1,
    divisible(X,Y1).

isprime(X) :-
    integer(X),
    X > 1,
    \+ divisible(X,2).

Merci d'avance 🙂

Je suis vraiment heureux que il ya des gens comme vous qui prennent de leur temps pour examiner la question, les réponses et de les comprendre et de contribuer. C'est vraiment quelque chose qui, je l'espère, je peux le faire. Bravo pour vous les gars
Je pense que tout mon temps sur stackoverflow a recevoir de l'aide et de ne pas aider les autres et cela me rend triste.
vous êtes la plupart de bienvenue (même si personnellement, je n'ai pas fait beaucoup ici); je suis sûr que vous aurez à payer de l'avant chaque fois que c'est possible pour vous.

OriginalL'auteur user3490561 | 2014-04-25

primes prolog

9

Je suis débutant dans le Prologue, mais a réussi à résoudre votre problème.
```
divisible(X,Y) :- 0 is X mod Y, !.

divisible(X,Y) :- X > Y+1, divisible(X, Y+1).

isPrime(2) :- true,!.
isPrime(X) :- X < 2,!,false.
isPrime(X) :- not(divisible(X, 2)).
```
Le principal problème était la déclaration X mod Y is 0. Prédicat is a deux (gauche et droite) des arguments, mais la gauche argument doit être une constante ou une variable qui est déjà unifiée au moment où le prédicat est en cours d'exécution. J'ai juste échangé ces valeurs. Le reste du code est pour vérifier le numéro 2 (qui est le premier) et le nombre de moins de 2 (qui ne sont pas des nombres premiers)

J'ai oublié de mentionner que la comparaison Y < X est buggé, parce que vous voulez tester tous les nombres entre 2 et X-1, cette comparaison inclut X.

Merci monsieur pour votre aide... beaucoup apprécié 🙂
Pas de problème. Ravi de vous aider.

OriginalL'auteur rareyesdev

Cette réponse est un suivi de @lefunction de la réponse précédente.

isPrime2/1 est aussi proche que possible de isPrime1/1 avec quelques changements cruciaux (mis en évidence ci-dessous):

isPrime2(2) :- 
!. 
isPrime2(3) :- 
!. 
isPrime2(X) :- 
X > 3, 
X mod 2 =\= 0, 
N_max est plafond(sqrt(X)), 
isPrime2_(X,3,N_max). 

isPrime2_(X,N,N_max) :- 
( N > N_max 
-> true 
; & lt; b>0 =\= X mod N, 
M est N + 2, 
isPrime2_(X,M,N_max) 
).

Nous allons requête!

?- temps(isPrime1(99999989)). 
% 99,999,990 inférences, 5.082 CPU 5.078 secondes (CPU à 100%, 19678881 Lèvres) 
vrai. 

?- temps(isPrime2(99999989)). 
% 20,002 des inférences, de 0,001 CPU 0.001 secondes (CPU à 100%, 13615185 Lèvres) 
vrai.

aïe, c'est rapide
Comment sur la parallélisation multi-cœurs?
sur ma machine le temps de ne pas s'inscrire.
Dans le sens de Gustavson de la loi: Choisissez une plus grande taille de problème.

OriginalL'auteur repeat

4

X mod Y is 0 échoue toujours, parce que pas d'expressions sur la gauche de is.

Changement de 0 is X mod Y, ou, mieux, à X mod Y =:= 0

merci monsieur... beaucoup appeciated 🙂

OriginalL'auteur Sergey Dymchenko

agarwaen accepté de répondre à n'est pas bien sur des grands nombres. C'est parce qu'il n'est pas de queue récursive (je pense). Aussi, vous pouvez accélérer le tout avec quelques faits à propos des nombres premiers.

1) 2 est le seul nombre premier pair

2) Tout nombre supérieur à la moitié de la première de ne pas répartir uniformément

isPrime1(2) :-
    !.
isPrime1(3) :-
    !.
isPrime1(X) :-
    X > 3,
    (  0 is X mod 2 
    -> false
    ;  Half is X/2,
       isPrime1_(X,3,Half)
    ).

isPrime1_(X,N,Half) :-
    (  N > Half 
    -> true
    ;  0 is X mod N
    -> false
    ;  M is N + 2,
       isPrime1_(X,M,Half)
    ).

1 ?- time(isPrime1(999983)). % 1,249,983 inferences, 0.031 CPU in 0.039 seconds (80% CPU, 39999456 Lips) true.

EDIT1

Est-il possible d'aller un pas plus loin? isPrime_/3 est plus efficace que isPrime2/1 parce qu'il compare uniquement précédemment sur les nombres premiers connus. Cependant, le problème est la création de cette liste.

allPrimes(Max,Y) :- 
    allPrimes(3,Max,[2],Y).

allPrimes(X,Max,L,Y) :-
    Z is X+2,
    N_max is ceiling(sqrt(X)),
    (  X >= Max 
    -> Y = L;
    (  isPrime_(X,L,N_max)
    -> append(L,[X],K),       %major bottleneck
       allPrimes(Z,Max,K,Y)
    ;  allPrimes(Z,Max,L,Y)
    )).

isPrime_(_,[],_).

isPrime_(X,[P|Ps],N_max) :-
    (  P > N_max  
    -> true     %could append here but still slow
    ;  0 =\= X mod P,
       isPrime_(X,Ps,N_max)
    ).

OriginalL'auteur lefunction

0

J'chose qui est élégant:
```
isPrime(A):-not((A1 is A-1,between(2,A1,N), 0 is mod(A,N))),not(A is 1).
```
1 n'EST PAS PREMIER NUMÉRO, mais si vous ne le pense pas il suffit de supprimer pas(Une est 1).

OriginalL'auteur Morticia A. Addams

Vous devez vous connecter pour publier un commentaire.