PDA

View Full Version : IsPrime Function



Nebula
08-27-2013, 06:16 AM
function IsPrime(Num: Integer): boolean;
var
h: Integer;
begin
if not (Num = 2) then
for h:= 2 to ceil(Num/2.0) do
begin
if floor(Num/extended(h)) = ceil(Num/extended(h)) then
break;
if h = ceil(Num/2.0) then
result := true;
end else
result := true;
end;

returns true if 'num' is a prime number

not sure what the usage of this would be but w/e i got bored so i made it

KingKong
08-27-2013, 12:09 PM
Thats a lot of floors/ceils/extended casts, all you need is a loop where i:= 3 to ceil(sqrt(num)) step 2 and check if num mod i equals 0

Turpinator
08-27-2013, 02:41 PM
Thats a lot of floors/ceils/extended casts, all you need is a loop where i:= 3 to ceil(sqrt(num)) step 2 and check if num mod i equals 0

So lets see if im getting this right...

checking to ensure its not 2 or 3 goes here. and greater than 4 right? (as that would cause a loop error ie a > b)
ceilsqrt := ceil(sqrt(num))
for i := 3 to ceilsqrt do
begin
result := num mod i = 0
if not result then exit;
end;

(that should be more efficient than my first write at it i believe.

lets try 11.
so ceil(sqrt(11)) = 4
set = [3, 4]
11 mod 3 = 2
11 mod 4 = 3
--> 11 is not prime?

12
set = [3, 4]
12 mod [3, 4] = [0, 0]

13
set = [3, 4]
13 mod [3, 4] = [1, 1]

14
set = [3, 4]
14 mod [3, 4] = [2, 2]

15
set = [3, 4]
15 mod [3, 4] = [0, 3]

skipping ahead...

37
set = [3, 4, 5, 6, 7]
37 mod [3, 4, 5, 6, 7] = [1, 1, 2, 1, 2]

yeah am i doing something wrong here?

okay. wrote a script to do this for me...

program prime;
var
num, i, ends: integer;
arr : TIntegerArray;
begin
for num := 2 to 50 do
begin
writeln(num)
if num > 3 then
begin
ends := ceil(sqrt(num));
setlength(arr, ends - 2);
for i := 3 to ends do
arr[i-3] := num mod i;
writeln(arr);
end
end;
end.

2
3
4
[]
5
[2]
6
[0]
7
[1]
8
[2]
9
[0]
10
[1, 2]
11
[2, 3]
12
[0, 0]
13
[1, 1]
14
[2, 2]
15
[0, 3]
16
[1, 0]
17
[2, 1, 2]
18
[0, 2, 3]
19
[1, 3, 4]
20
[2, 0, 0]
21
[0, 1, 1]
22
[1, 2, 2]
23
[2, 3, 3]
24
[0, 0, 4]
25
[1, 1, 0]
26
[2, 2, 1, 2]
27
[0, 3, 2, 3]
28
[1, 0, 3, 4]
29
[2, 1, 4, 5]
30
[0, 2, 0, 0]
31
[1, 3, 1, 1]
32
[2, 0, 2, 2]
33
[0, 1, 3, 3]
34
[1, 2, 4, 4]
35
[2, 3, 0, 5]
36
[0, 0, 1, 0]
37
[1, 1, 2, 1, 2]
38
[2, 2, 3, 2, 3]
39
[0, 3, 4, 3, 4]
40
[1, 0, 0, 4, 5]
41
[2, 1, 1, 5, 6]
42
[0, 2, 2, 0, 0]
43
[1, 3, 3, 1, 1]
44
[2, 0, 4, 2, 2]
45
[0, 1, 0, 3, 3]
46
[1, 2, 1, 4, 4]
47
[2, 3, 2, 5, 5]
48
[0, 0, 3, 0, 6]
49
[1, 1, 4, 1, 0]
50
[2, 2, 0, 2, 1, 2]

I see no pattern or commonality between the 'output' of primes or composites.

masterBB
08-27-2013, 06:17 PM
I see no pattern or commonality between the 'output' of primes or composites.

function IsPrime(Num: Integer): boolean;
var
h: Integer;
begin
if not (Num = 2) then
for h:= 2 to ceil(Num/2.0) do
if Num/h = ceil(Num/extended(h)) then
Exit;
Result := True;
end;

function IsPrime2(Num: Integer): boolean;
var
i, ceilsqrt: Integer;
begin
ceilsqrt := Ceil(Sqrt(Num));

if Num > 2 then
for i := 2 to ceilsqrt do
if ((num mod i) = 0) then
exit;

Result := True;
end;

procedure PrimeTest;
var
Iterator: Integer;
p1Result, p2Result: String;
begin
for Iterator := 2 to 50 do
begin
if(IsPrime(Iterator))then
p1Result := p1Result + ToStr(Iterator) + ', ';
if(IsPrime2(Iterator))then
p2Result := p2Result + ToStr(Iterator) + ', ';
end;

writeln(p1Result);
writeln(p2Result);
end;

begin
PrimeTest();
end.

Nebula
08-27-2013, 06:33 PM
I wrote a bad piece of code feelsbadman.jpg

my function's still the best

reported for thread hijacking

#yohojo4admin (http://villavu.com/forum/usertag.php?do=list&action=hash&hash=yohojo4admin)

Turpinator
08-27-2013, 07:00 PM
function IsPrime(Num: Integer): boolean;
var
h: Integer;
begin
if not (Num = 2) then
for h:= 2 to ceil(Num/2.0) do
if Num/h = ceil(Num/extended(h)) then
Exit;
Result := True;
end;

function IsPrime2(Num: Integer): boolean;
var
i, ceilsqrt: Integer;
begin
ceilsqrt := Ceil(Sqrt(Num));

if Num > 2 then
for i := 2 to ceilsqrt do
if ((num mod i) = 0) then
exit;

Result := True;
end;

procedure PrimeTest;
var
Iterator: Integer;
p1Result, p2Result: String;
begin
for Iterator := 2 to 50 do
begin
if(IsPrime(Iterator))then
p1Result := p1Result + ToStr(Iterator) + ', ';
if(IsPrime2(Iterator))then
p2Result := p2Result + ToStr(Iterator) + ', ';
end;

writeln(p1Result);
writeln(p2Result);
end;

begin
PrimeTest();
end.

Ahh. so it has to start at 2. well... that would eliminate all the evens right out.

KingKong
08-27-2013, 10:50 PM
@masterBB if Num > 2 then ...

that would result as true for numbers less than 2, which are not actually primes

shaaneson
10-09-2013, 10:58 AM
Thank you vet much for your valuable contribution. keep sharing info.

slacky
10-19-2013, 05:58 AM
A prime is never divisible by 2, except 2 it self. So do a simple check first to save of some time.
Taken from SCARExt (http://github.com/WarPie/SCARExt/blob/master/src/XT.Math.pas#L245)

function IsPrime(n: Integer): Boolean;
var i:Integer; Hi: Single;
begin
if (n = 2) then Exit(True);
if (n mod 2 = 0) or (n<=1) then Exit(False);
Hi := Sqrt(n)+1;
i := 3;
while i <= Hi do begin
if ((n mod i) = 0) then Exit(False);
i := i + 2;
end;
Result := True;
end;