Discuss and collaborate on GML scripts

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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

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

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

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

a..... thanks

well i had a shot

any ways a nice script you have there

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,239

That's pretty slick, Yourself.

*Abusing forum power since 1986.*

Offline

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

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

Offline

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,239

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

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

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

**lostdarkwolf****Member**- Registered: 2015-11-19
- Posts: 31

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

**xot****Administrator**- Registered: 2007-08-18
- Posts: 1,239

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

**gnysek****Member**- Registered: 2011-12-29
- Posts: 36

So, for 2022, most up-to-date version (including <= fix) will be:

```
/// @param {real} n number to check
/// @returns {bool}
function is_prime(n) {
var a = [0, 2, 0, 4, 0, 2, 0, 2, 0, 2], p, m;
if (n mod 2 == 0) return false;
if (n mod 3 == 0) return false;
p = 5;
m = sqrt(n);
while (p <= m) {
if (n mod p == 0) return false;
p += a[p mod 10];
}
return true;
}
```

??

*Last edited by gnysek (2022-09-20 12:26:37)*

Offline

Pages: **1**