GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2008-02-13 02:19:37

atarian
Member
Registered: 2008-01-07
Posts: 9

Is_Prime

Hi everyone
this is a new script of my that i made for no apparent reason.
it finds out if a number is a prime

#define is_prime
/* is_prime(x)
**
** Uses: 
** for finding prime numbers
**
** Arguments:
** x            the number to check if it's a prime
**
** Returns:
** Val         true if the number is a prime false if it's not
**
*/

var _p,val;
_p = argument0
val = true
i = 2
while (val = true)&&(i!=_p-1)
{
if (frac(_p/i) = 0)
{
val = false
}
i += 1
}
return val;

can you please tell me what you tihnk

Offline

#2 2008-02-13 02:33:38

Yourself
Member
Registered: 2007-10-09
Posts: 48

Re: Is_Prime

This would be much faster:

var a, p, m;
a[1] = 2; a[3] = 4; a[5] = 2; a[7] = 2; a[9] = 2;
if (argument0 mod 2 == 0) return false;
if (argument0 mod 3 == 0) return false;
p = 5;
m = sqrt(argument0);
while (p < m) {
    if (argument0 mod p == 0) return false;
    p += a[p mod 10];
}
return true;

Last edited by Yourself (2008-02-13 02:34:09)

Offline

#3 2008-02-13 03:01:39

atarian
Member
Registered: 2008-01-07
Posts: 9

Re: Is_Prime

a..... thanks
well i had a shot

any ways a nice script you have there

Offline

#4 2008-02-13 06:20:30

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Is_Prime

That's pretty slick, Yourself.


Abusing forum power since 1986.

Offline

#5 2008-08-20 17:51:49

Scepheo
Member
Registered: 2008-08-18
Posts: 1

Re: Is_Prime

Yourself, your script isn't completely correct as it would return false for 2, (2 mod 2 =0) which is a prime.

Offline

#6 2008-08-20 20:51:19

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Is_Prime

Good eyes. The funny thing is that BOTH scripts report 2 as non-prime. Yourself's reports 2 and 3 as non-prime, and 1 as prime. Atarian's locks up if you try to test 1 or a non-integer.


Abusing forum power since 1986.

Offline

#7 2009-01-05 18:18:24

xDanielx
Member
Registered: 2009-01-02
Posts: 38

Re: Is_Prime

Negative numbers is also an issue. Here's a modification of Yourself's script that should work in all cases --

if (argument0 < 4) return (argument0 > 1);
if !(argument0 mod 2 && argument0 mod 3) return false;

var a, m, d;
a[1] = 2; a[3] = 4; a[5] = 2; a[7] = 2; a[9] = 2;
m = sqrt(argument0);

for (d = 5; d < m; d += a[d mod 10])
if (argument0 mod d == 0)
return false;

return true;

Last edited by xDanielx (2009-01-05 18:20:52)

Offline

#8 2019-08-11 05:00:50

lostdarkwolf
Member
Registered: 2015-11-19
Posts: 23

Re: Is_Prime

Sorry to grave dig, but I noticed that yourself's script, and xDanielx's modification of yourself's script, are both flawed. According to both scripts, the following numbers are incorrectly considered as prime numbers. 25, 49, 121, and 169 (first four only). atarian's script can handle negative numbers, and it can be seemingly flawless with the following inclusion:

_p = argument0 // existing line
if (_p=2) return true // new line
val = true // existing line 

Offline

#9 2019-08-11 13:20:00

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Is_Prime

Ten years has to be a resurrection record.

I believe the main problem with Yourself's script is just a typo:

while (p < m)

... should be:

while (p <= m)

xDanielx's modification has the same problem in the conditional expression of the for statement. It should be:

for (d = 5; d <= m; d += a[d mod 10])

As for negative numbers, they are not in the set of natural numbers and thus by definition cannot be prime. The test in the first line of xDanielx's script takes care that.

Either of those scripts are good with corrections (including additional tests at the start for Yourself's). The script by atarian is just way too slow by comparison.

I would normally never question Yourself's math because he is a mathematician specializing in number theory — but we all make mistakes.


Abusing forum power since 1986.

Offline

Board footer

Powered by FluxBB