I tested with this "primes" function in Nial, but even my first attempt
at generating primes in J, The PrimesUntil verb, is considerably better.
At 10000 primes Nial got in trouble. At 20000 primes Nial crashed.
https://en.wikipedia.org/wiki/Nial#Explanation
/Erling
Den 2017-09-17 kl. 20:34, skrev Erling Hellenäs:
"Currently, arguments larger than2^31are tested to be prime according
to a probabilistic algorithm (Miller-Rabin)"
http://www.jsoftware.com/docs/help804/dictionary/dpco.htm
Miller–Rabin primality test
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
This means that sometimes, for arguments larger than 2^31, 1 p: y will
give an incorrect result?
/Erling
On 2017-09-17 19:28, Erling Hellenäs wrote:
Strange things happen here. It works but give incorrect results. I
just changed F to lower case to put it through my tests. Not sure
what might happen here. I have J 8.04 on this machine. 64 bit.
I never doubted that p: was good. I just thought that since it was a
Quora challenge that using p: would not be a good idea, since the
algorithm used in p: is not known to the audience. It also seemed
like some kind of cheating, like using a subroutine someone else
wrote to solve half the problem.
Well, I also thought p: would have to generate the array of primes
for each call, but it's obviously not the case. There is a formula
which does the trick? Or a hash table of primes?
thru=: <. + >:@>. i.@- <.
biggap=: {~ 0 1 - [: (i. <./) 2 -/\ ]
f=: [: thru/ 1 _1 + [: biggap <./ >. >./ <. thru&.(p:inv)
s=: 10 f 100
s
20 21 22
>./90 91 92 93 94 95 96 = s
|length error: scriptd
| >./90 91 92 93 94 95 96 =s
|[-5] j:\j64-803-user\projects\quoraraul.ijs
inv
^:_1
Cheers,
Erling
On 2017-09-17 17:38, Raul Miller wrote:
Yes. :)
When J provides a mechanism for something it is usually worth trying.
Sometimes you can write something faster, but usually J's approach
will be useful.
For example, in this case, consider this approach:
thru=: <. + >:@>. i.@- <.
biggap=: {~ 0 1 - [: (i. <./) 2 -/\ ]
F=: [: thru/ 1 _1 + [: biggap <./ >. >./ <. thru&.(p:inv)
There will be cases where another approach could be more efficient,
but it performs reasonably well.
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
