Prolog-Programm Um Zu Überprüfen, Ob Eine Zahl Eine Primzahl Ist

Schrieb ich das folgende Programm basiert auf der Logik, dass eine Primzahl ist nur teilbar durch 1 und sich selbst. Also ich gehe einfach durch den Prozess der Teilung, um alle zahlen, die größer als eins und kleiner als es selbst, aber ich glaube, ich habe ein problem, seit dem bekomme ich alle eingegebenen zahlen als wahr. Hier ist mein 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).

Vielen Dank im Voraus 🙂

Ich bin wirklich froh, dass es Menschen gibt wie dich, die nehmen würde aus Ihrer Zeit zur überprüfung der Frage, die Antworten und Sie zu verstehen und zu leisten. Es ist wirklich etwas, dass ich hoffe, dass ich das tun kann. Ein dickes Lob für Euch
Ich glaube, alle, die meine Zeit auf stackoverflow war, die Hilfe erhalten, und nicht, anderen zu helfen und das macht mich traurig.
Sie sind das meiste willkommen, (obwohl ich persönlich nicht viel hier); ich bin sicher, dass Sie ' ll pay it forward, wenn es möglich ist für Sie.

InformationsquelleAutor user3490561 | 2014-04-25

  1. 9

    Ich bin ein Anfänger in Prolog, aber Sie schaffte es, Ihr problem zu lösen.

    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)).

    Zentrales Thema war die Aussage X mod Y is 0. Prädikat is hat zwei (Links und rechts) - Argumente, aber das linke argument eine Konstante oder eine variable, die bereits unified im moment, dass das Prädikat ausgeführt wird. Ich habe gerade vertauscht diese Werte. Der rest des Codes ist für die Prüfung Nummer 2 (prime) und Zahl, die kleiner als 2 sind keine Primzahlen)

    Ich vergaß zu erwähnen, dass der Vergleich Y < X buggy ist, weil Sie testen möchten, die für alle zahlen zwischen 2 und X-1, der Vergleich beinhaltet X.

    Danke sir für deine Hilfe... sehr geschätzt 🙂
    Kein problem. Froh zu helfen.

    InformationsquelleAutor rareyesdev

  2. 5

    Diese Antwort ist ein follow-up zu @lefunction die Vorherige Antwort.

    isPrime2/1 ist so nah wie möglich an isPrime1/1 mit ein paar entscheidenden änderungen (unten hervorgehoben):

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

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

    Let ' s Abfrage!

    ?- Zeit(isPrime1(99999989)). 
% 99,999,990 Rückschlüsse 5.082 CPU in 5.078 Sekunden (100% CPU, 19678881 Lippen) 
wahr. 

?- Zeit(isPrime2(99999989)). 
% 20,002 Rückschlüsse 0.001 CPU in 0.001 Sekunden (100% CPU, 13615185 Lippen) 
wahr.
    Huch, das ist schnell
    Wie etwa die Parallelisierung auf multi-cores?
    auf meinem Rechner die Zeit nicht registrieren.
    Im Sinne von Gustavson ' s law: Wählen Sie eine größere Größe problem.

    InformationsquelleAutor repeat

  3. 4

    X mod Y is 0 schlägt immer fehl, weil keine Ausdrücke erlaubt, auf der linken Seite der is.

    Änderung 0 is X mod Y oder, besser, zu X mod Y =:= 0

    Dank sir... viel appeciated 🙂

    InformationsquelleAutor Sergey Dymchenko

  4. 3

    agarwaen die akzeptierte Antwort nicht gut auf große zahlen. Dies ist, weil es ist nicht tail-rekursiv (glaube ich). Auch können Sie die Geschwindigkeit alles mit ein paar Fakten über Primzahlen.

    1) 2 ist der nur noch Primzahl

    2) Jede Zahl, die größer als die Hälfte der ursprünglichen nicht gleichmäßig aufzuteilen

    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

    Ist es möglich, es zu nehmen ein Schritt weiter? isPrime_/3 ist effizienter als isPrime2/1, weil es vergleicht nur die bisher bekannten Primzahlen. Das problem jedoch ist die Generierung dieser 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)
    ).

    InformationsquelleAutor lefunction

  5. 0

    Ich Sache ist die elegante Art und Weise:

    isPrime(A):-not((A1 is A-1,between(2,A1,N), 0 is mod(A,N))),not(A is 1).

    1 IST KEINE PRIMZAHL, aber wenn Sie nicht denken, also einfach löschen nicht(1).

    InformationsquelleAutor Morticia A. Addams

Schreibe einen Kommentar