- Make a loop through all positive integers less than the (floor of) the square root of the given integer. i.e if we want to find if 48 is prime, then we just need to check to see if 2 3 4 5 or 6 divide it.
- Loop through the numbers. Use "%" to check the remainder on division. If remainder is zero, break out of the loop and declare our number not prime.
- If we reach the end of the loop, we know our number is prime.
In J, there isn't really looping. I had a good think how to do the primality test and the only way I found (without looking at anyone else's code) was to create two functions (verbs). One is a dyadic verb, and the other monadic.
The first verb shall be called ISDIV (meaning "is divisible"):
ISDIV=: dyad :'0=x|y'
I think this function is pretty clear. It checks if y divided by x leaves remainder zero. Or checks if y is divisible by x.
2 ISDIV 4
1
because 4 is divisible by 2. Here one equates to true, 0 to false.
Now we do the dyadic verb, which is a little more complicated:
ISPRIME =: monad : '1=#((1+i.>.y^0.5) ISDIV y) #(1+i.(>.y^0.5))'
What's going on here? Well, we check if y ISDIV by all the values up to >.y^0.5, that is, up to the square root of y. This will give us a list of 0's and 1's, corresponding to divisible and not divisible. In teh case of zero
0 ISDIV y
outputs zero. With our list we now use the dyadic verb "#" (not to be confused with monadic "#", which is tally). This verb copies the 1's form the left operand to the list, which is the right operand. In effect it gives us only those numbers which divide y. More importantly, it gives us the length of the list of those numbers. This is what the monadic "#" at the front means. It gives us the length of the list of divisors of y. We already know that 1 is in the list. So we check to see if the length of this list equals 1, "1=#...". If it does the output is 1 (true), else output is 0 (false).
For example:
ISPRIME 13
1
ISPRIME 70
0
Well that was my first attempt at a primality test. I would have liked to have written it with only one function. But my J powers are still weak. I can also already see slight flaws. There is no need to test if 1 is a divisor of a number, so the test of this is wasted. Not a big problem, but...
The verb ISPRIME could easily be modified to not only give us the primality of y, but to output the list of proper divisors.
DIVLIST =: monad : '((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'
DIVLIST 6
1 2 3
We could go even further, and calculate sigma(y). That is, the sum of all the proper divisors.
SIG=: monad : '+/((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'
All we did was append the +/ on the front. Wait, so now we can test if y is perfect.
ISPERFECT =: monad : 'Y = SIG y'
ISPERFECT 6
1
ISPERFECT 28
1
ISPERFECT 18
0
No comments:
Post a Comment