Selasa, 12 Agustus 2008

MENGECEK BILANGAN PRIMA

Mungkin anda anak SMA atau yang berminat di DELPHI source program sederhana berikut dapat membantu anda dalam fungsi dalam program Delphi yang mengecek suatu bilangan prima. Fuction ini dapat di sisipkan dalam program utama. Sourcenya sebagai berikut.

Source Pertama

function IsPrime(Number: Cardinal): Boolean;

var

cDivisor,

cMax : Cardinal;

begin

Result := False;

if Number and 1 = 0 then

Exit;

cMax := Trunc(Sqrt(Number)) + 1;

cDivisor := 3;

while cMax > cDivisor do begin

if Number mod cDivisor = 0 then

Exit;

Inc(cDivisor, 2);

if Number mod cDivisor = 0 then

Exit;

Inc(cDivisor, 4);

end;

Result := True;

end;

Source Kedua

function IsPrime(Nnumber: Cardinal): Boolean; register;

// Test if N is prime, do some small Strong Pseudo Prime test in certain bounds

// Copyright (c) 2000 Hagen Reddmann, don't remove

asm

TEST EAX, 1 // Odd(N)?

JNZ @@1

CMP EAX, 2 // N = 2?

SETE AL

RET

@@1:

CMP EAX, 73 // N JB @@C

JE @@E // N = 73?

PUSH ESI

PUSH EDI

PUSH EBX

PUSH EBP

PUSH EAX // Save N as Param for @@5

LEA EBP, [EAX - 1] // M = N -1, Exponent

MOV ECX, 32 // Calc remaining Bits of M and shift M'

MOV ESI, EBP

@@2:

DEC ECX

SHL ESI,1

JNC @@2

PUSH ECX Save Bits as Param for @@5

PUSH ESI Save M' as Param for @@5

CMP EAX, 08A8D7Fh // N = 9080191?

JAE @@3

// Now if (N MOV EAX, 31

CALL @@5 // 31^((N - 1)(2^s)) mod N

JC @@4

MOV EAX, 73 // 73^((N - 1)(2^s)) mod N

PUSH OFFSET @@4

JMP @@5

// Now if (N @@3: MOV EAX, 2

CALL @@5

JC @@4

MOV EAX, 7

CALL @@5

JC @@4

MOV EAX, 61

CALL @@5

@@4:

SETNC AL

ADD ESP, 4 * 3

POP EBP

POP EBX

POP EDI

POP ESI

RET

// Do a Strong Pseudo Prime Test

@@5:

MOV EBX, [ESP + 12] // N on stack

MOV ECX, [ESP + 8] // Remaining Bits

MOV ESI, [ESP + 4] // M'

MOV EDI, EAX // T = b, temp. Base

@@6:

DEC ECX

MUL EAX

DIV EBX

MOV EAX, EDX

SHL ESI, 1

JNC @@7

MUL EDI

DIV EBX

AND ESI, ESI

MOV EAX, EDX

@@7:

JNZ @@6

CMP EAX, 1 // b^((N - 1)(2^s)) mod N = 1 mod N?

JE @@A

@@8:

CMP EAX, EBP // b^((N - 1)(2^s)) mod N = -1 mod N?, EBP = N -1

JE @@A

DEC ECX // Second part to 2^s

JNG @@9

MUL EAX

DIV EBX

CMP EDX, 1

MOV EAX, EDX

JNE @@8

@@9:

STC

@@A:

RET

@@B:

DB 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71

@@C:

MOV EDX, OFFSET @@B

MOV ECX, 18

@@D:

CMP AL,[EDX + ECX]

JE @@E

DEC ECX

JNL @@D

@@E:

SETE AL

end;

Tidak ada komentar: