
Joined: Aug 2003
Posts: 314
Fjord artisan

OP
Fjord artisan
Joined: Aug 2003
Posts: 314 
An isprime operator or $prime identifier would be good




Joined: Feb 2003
Posts: 2,812
Hoopy frood

Hoopy frood
Joined: Feb 2003
Posts: 2,812 
What formula do you recommend it use?
It can take years to determine if a number is prime or not.
Well. At least I won lunch. Good philosophy, see good in bad, I like!




Joined: Aug 2003
Posts: 314
Fjord artisan

OP
Fjord artisan
Joined: Aug 2003
Posts: 314 
There are many algorithms out there for such a calculation, none that I can recall the name of, but I was just making a suggestion. I didn't really consider the mechanics behind it. Sure it would take years to determine if a very large number was prime but what if there was some limitation to the identifier?




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
It doesn't take years, it takes at most minutes, at least for the largest number mIRC supports. Plus, I must say if "isurl" was getting such high praise, I really don't see why mIRC shouldn't have an "isprime" it could be very useful. In the meantime, here is an algorithm that is pretty fast, any faster algorithms I know of would require so much coding (simulating vectors and such) that in mIRC scripting they would be slow. alias isprime {
if (2 // $1  $int($1) != $1) { return $false }
var %i = 3, %s = $sqrt($1)
while (%i <= %s) {
if (%i // $1) return $false
inc %i 2
}
return $true
}
It's not nearly as fast as some other methods, but it works, and it works especially well for "common" numbers, for example to determine if 13115117933 is prime it took roughly 4 seconds, and that one requires a decent amount of work seeing as how, no it is no prime and the factor is 75289 which obviously required a decent amount of work to figure out. If you are trying to determine if a number that is less than 2^321 is prime, than that alias will work just fine. But like I said, if an isurl operator is useful enough to be added to mIRC, then I'd say isprime is. Isprime could be coded much better if it were done in C++ code than in mIRC scripting because you could use more complex testing.




Joined: Aug 2003
Posts: 314
Fjord artisan

OP
Fjord artisan
Joined: Aug 2003
Posts: 314 
Yes, about the complexity of C++, that's why I suggested it. I came up with pretty much the same calculation (looping from 1 to $sqrt(N)) but if there is a method on C++, it would be useful to see included. Why the extra 2 // $1 though? That would be checked the first time the loop is run (if you began with %i equal to 2)




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
Well, the reason is, if $1 is not divisible by 2, then it is not divisible by any multiple of 2, so instead of trying 2,3,4,5,6,7,8,... I set it up to do 2,3,5,7,9,... and if I started with %i = 2, the /inc %i 2 would make it 4, not 3, and then the next increment would make it 6 not 5. So I figured it is just easier to start at 3.




Joined: Dec 2002
Posts: 343
Pandimensional mouse

Pandimensional mouse
Joined: Dec 2002
Posts: 343 
I just use something like the below. By the way, there is a significant amount of people who consider one prime, so ignore that.
isprime { var %t $ticks if ($len($1) > 19) { return $ $+ error  halt } if ($1 !isnum) { return $ $+ error  halt } if ($1 < 1) { return $false  halt } if ($1 != $int($1)) { return $false  halt } if ($istok(1 2 3 5 7,$1,32)) { return $true  halt } if (2 // $1)  (3 // $1)  (5 // $1) { return $false  halt } var %n 1 var %a $sqrt($1) while (%n < %a) { inc %n 6 if (%n // $1) { return $false $calc($ticks  %t)  halt } } return $true $calc($ticks  %t) }




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
Just thought of a way to make that a bit faster. alias isprime {
if ($1 == 2) { return $true }
if (2 // $1  $int($1) != $1) { return $false }
var %i = 3, %s = $sqrt($1)
if ($int(%s) == %s) return $false
while (%i <= %s) {
if (%i // $1) return $false %i
inc %i 2
}
return $true
}
If the square root of a number is an integer, then the number can not be prime, because it can be divided by an integer, namely its square root, and get an integer answer. Additionally, stupid me, I forgot to include the special case of 2, which is prime. See using C++, it could be done much faster. Division is a very costly operation, addition/subtraction are much faster. There is a very basic (I remember learning it in about 6th grade) algorithm that is called the Sieve of Eratosthenes. Unfortunately, that algorithm requires an array and since mIRC doesn't support arrays, even though it is a very simple algorithm, it is difficult to implement in an mIRC script.




Joined: Feb 2003
Posts: 2,812
Hoopy frood

Hoopy frood
Joined: Feb 2003
Posts: 2,812 
What if you only try dividing against numbers that end in 1 or 3 or 7 or 9, only? This should double the speed or better. alias isprime {
if ($1 == 2) { return $true }
if (2 // $1  $int($1) != $1) { return $false }
var %s = $sqrt($1)
if ($int(%s) == %s) return $false
var %i = 0, %s = $int($calc(%s / 10))
while (%i <= %s) {
if (%i $+ 1 // $1) return $false
if (%i $+ 3 // $1) return $false
if (%i $+ 7 // $1) return $false
if (%i $+ 9 // $1) return $false
inc %i
}
return $true
} I'm not sure if this would miss anything at the start or end, but should be accurate for the bulk of the loop. Extra coding is probably necessary. I just used your existing code, I would personally write it slightly differently. I would also check if (*1 iswm $1)  (*3 iswm $1)  (*7 iswm $1)  (*9 iswm $1) or just add to your check if (2 // $1  $int($1) != $1  *5 iswm $1) { return $false }.  Raccoon Heh Doomstars, I just noticed that myself.
Last edited by Raccoon; 28/08/03 10:23 PM.
Well. At least I won lunch. Good philosophy, see good in bad, I like!




Joined: Dec 2002
Posts: 343
Pandimensional mouse

Pandimensional mouse
Joined: Dec 2002
Posts: 343 
That's basically what I posted. Except 5's are hit now and then.




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
Well your snippet there misses a ton of prime numbers. Just doing a little test of primes from 1 ... 100 your algorithm missed: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
All of those are prime but your algorithm says they are not.
Doomstars is also broken. His works fine for 1 ... 100, but if I do 1 ... 500, then his identifies 121 187 253 289 319 341 391 407 451 473 493 as prime numbers, however, none of those are actually prime. The obvious one would be 121 which is 11*11.
You both had interesting ideas, but they just don't work.




Joined: Feb 2003
Posts: 2,812
Hoopy frood

Hoopy frood
Joined: Feb 2003
Posts: 2,812 
I think my method is accurate, but there's an error in my syntex somewhere. That's every prime number between 3100, so it's clearly hanging up on something.
Well. At least I won lunch. Good philosophy, see good in bad, I like!




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
Indeed, I see the problem, if ($1 // %i $+ 1) return $false if ($1 // %i $+ 3) return $false if ($1 // %i $+ 7) return $false if ($1 // %i $+ 9) return $false You had those backwards. (%i $+ 1 // $1) // is "v2 is a multiple of v1" so you need to reverse it. However, even after doing that it still misses a bunch.
These are reported as notprime (composite): 3 7 And these are reported as prime: 35 39 45 5155 57 63 65 69 75 77 85 87 91 93 95 99




Joined: Feb 2003
Posts: 2,812
Hoopy frood

Hoopy frood
Joined: Feb 2003
Posts: 2,812 
ay, an initial check against 3, 5, 7 and 11 should be made it seems.
Well. At least I won lunch. Good philosophy, see good in bad, I like!




Joined: Dec 2002
Posts: 343
Pandimensional mouse

Pandimensional mouse
Joined: Dec 2002
Posts: 343 
I think the below is correct, but I could be wrong again. But down to an issue. I think $isprime would be a good identifier, but how many else would use it? Hopefully $isprime(number,0) would count 1 as not a prime. And $isprime(number,1) would count 1 as a prime. There are some who consider one as a prime. Why they do, it's because of the theory the numbers 1, 2, and 3 compose all of reality. isprime { var %t $ticks if ($len($1) > 19) { return $ $+ error  halt } if ($1 !isnum) { return $ $+ error  halt } if ($1 < 1) { return $false  halt } if ($1 != $int($1)) { return $false  halt } if ($istok(1 2 3,$1,32)) { return $true  halt } if (2 // $1) { return $false  halt } var %n 1 var %a $sqrt($1) while (%n < %a) { inc %n 2 if (%n // $1) { return $false $calc($ticks  %t)  halt } } return $true $calc($ticks  %t) }




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
Hopefully $isprime(number,0) would count 1 as not a prime. And $isprime(number,1) would count 1 as a prime. There are some who consider one as a prime. Why they do, it's because of the theory the numbers 1, 2, and 3 compose all of reality. I hope it doesn't. Yes some peope say that, and some people say that 0 is both even and odd. But guess what? Those people are wrong. Thats like saying "well some people go around saying 2+2 is 5, so there should be a $calc(2+2,1) that makes it say 5." Just because people say it doesn't make it true; 1 is NOT prime. mIRC should not include an identifier that will give a wrong answer, and saying 1 is prime is wrong.




Joined: Dec 2002
Posts: 343
Pandimensional mouse

Pandimensional mouse
Joined: Dec 2002
Posts: 343 
I'm not wrong. And I'm not going to argue.




Joined: Dec 2002
Posts: 2,809
Hoopy frood

Hoopy frood
Joined: Dec 2002
Posts: 2,809 
I didn't say you were wrong, I know there are people who say 1 is prime, I'm saying THOSE people are wrong.




Joined: Dec 2002
Posts: 343
Pandimensional mouse

Pandimensional mouse
Joined: Dec 2002
Posts: 343 
And I agree one can be considered prime. Which is one method. I'm not going to get into this discussion, it will just be a huge arguement.




Joined: Feb 2003
Posts: 2,812
Hoopy frood

Hoopy frood
Joined: Feb 2003
Posts: 2,812 
One is neither prime NOR not prime.
$isprime(1) should raise an error, just as $calc(1 / 0) causes a Divide By Zero. * $isprime(): Isprimed By One.
One might say that 1 / 0 == Zero, while others say it == One.
Neither are right, neither are wrong.
 Raccoon
Well. At least I won lunch. Good philosophy, see good in bad, I like!




