Is_Prime

atarian · 2008-02-13 02:19:37

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

Expand#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

Yourself · 2008-02-13 02:33:38

This would be much faster:

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

atarian · 2008-02-13 03:01:39

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

any ways a nice script you have there

xot · 2008-02-13 06:20:30

That's pretty slick, Yourself.

Scepheo · 2008-08-20 17:51:49

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

xot · 2008-08-20 20:51:19

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.

xDanielx · 2009-01-05 18:18:24

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

Expandif (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)

lostdarkwolf · 2019-08-11 05:00:50

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:

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

xot · 2019-08-11 13:20:00

Ten years has to be a resurrection record.

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

Expandwhile (p < m)

... should be:

Expandwhile (p <= m)

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

Expandfor (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.

gnysek · 2022-09-20 12:24:22

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

Expand/// @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)

GMLscripts.com

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

Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

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

Re: Is_Prime

#10 2022-09-20 12:24:22

Re: Is_Prime

Board footer