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,
--
Raul
On Sun, Sep 17, 2017 at 11:04 AM, Erling Hellenäs
<erl...@erlinghellenas.se> wrote:
> My first version easily handles 20 000 000. And I thought the second would
> be faster. Lol. J seems to have a very efficient way to see if a number is a
> prime.
>
> timespacex'2 f 20000000'
>
> 12.2883 5.36873e8
>
>
> /Erling
>
>
>
> On 2017-09-17 16:22, Erling Hellenäs wrote:
>>
>> It takes quite some time at 200000 and more. Due to PrimesUntil, it seems.
>>
>> timespacex'2 f 2000'
>>
>> 0.0121769 42240
>>
>> timespacex'2 f 20000'
>>
>> 0.426833 533760
>>
>> timespacex'2 f 200000'
>>
>> 30.0596 4.20378e6
>>
>> timespacex'PrimesUntil 200000'
>>
>> 30.0592 4.19981e6
>>
>>
>> /Erling
>>
>>
>> On 2017-09-17 16:05, Erling Hellenäs wrote:
>>>
>>> Hi Raul !
>>>
>>> This is what happens when I run it in a clean JQT. I added a timespecex
>>> call. Not sure what might happen for you.
>>>
>>> Cheers,
>>> Erling
>>>
>>> Prime=: [: -. [: +./0 = [ | ]
>>>
>>> (,2) Prime 3
>>>
>>> 1
>>>
>>> NB. 1
>>>
>>> 2 3 Prime 4
>>>
>>> 0
>>>
>>> NB. 0
>>>
>>> 2 3 Prime 5
>>>
>>> 1
>>>
>>> NB. 1
>>>
>>> 2 3 5 Prime 6
>>>
>>> 0
>>>
>>> NB. 0
>>>
>>> PrimesUntil=: 3 : 0
>>>
>>> primes=.i.0
>>>
>>> n=. 2 + i. y - 1
>>>
>>> for_i. n do.
>>>
>>> primes=.primes,(primes Prime i) # i
>>>
>>> end.
>>>
>>> primes
>>>
>>> )
>>>
>>> PrimesUntil 5
>>>
>>> 2 3 5
>>>
>>> NB. 2 3 5
>>>
>>> PrimesUntil 10
>>>
>>> 2 3 5 7
>>>
>>> NB. 2 3 5 7
>>>
>>> PrimesUntil 11
>>>
>>> 2 3 5 7 11
>>>
>>> NB. 2 3 5 7 11
>>>
>>> PrimesInRange=: 4 : 0
>>>
>>> n=. PrimesUntil y
>>>
>>> (n >: x)# n
>>>
>>> )
>>>
>>> 7 PrimesInRange 11
>>>
>>> 7 11
>>>
>>> NB. 7 11
>>>
>>> 7 PrimesInRange 10
>>>
>>> 7
>>>
>>> NB. 7
>>>
>>> 8 PrimesInRange 10
>>>
>>>
>>> NB. i.0
>>>
>>> AddStartRangeIfNotThere=: (([ ~: 1 {. ]) # [) , ]
>>>
>>> 3 AddStartRangeIfNotThere 3 5 7 11
>>>
>>> 3 5 7 11
>>>
>>> NB. 3 5 7 11
>>>
>>> 8 AddStartRangeIfNotThere i.0
>>>
>>> 8
>>>
>>> NB. 8
>>>
>>> AddEndRangeIfNotThere=: ] , ([ ~: _1 {. ]) # [
>>>
>>> 11 AddEndRangeIfNotThere 3 5 7 11
>>>
>>> 3 5 7 11
>>>
>>> NB. 3 5 7 11
>>>
>>> 10 AddEndRangeIfNotThere 8
>>>
>>> 8 10
>>>
>>> NB. 8 10
>>>
>>> SequenceLengths=: 1 + (1 }. ]) - _1 }. ]
>>>
>>> SequenceLengths 3 5 7 11
>>>
>>> 3 3 5
>>>
>>> NB.3 3 5
>>>
>>> SequenceLengths 8 10
>>>
>>> 3
>>>
>>> NB. 3
>>>
>>> FirstInLongestSequence=: '' $ (([ = [: >./ [) , 0:) # ]
>>>
>>> 3 3 5 FirstInLongestSequence 3 5 7 11
>>>
>>> 7
>>>
>>> NB. 7
>>>
>>> 3 FirstInLongestSequence 8 10
>>>
>>> 8
>>>
>>> NB. 8
>>>
>>> SequenceIndices=: ] + [: i. [: >./ [
>>>
>>> 3 3 5 SequenceIndices 7
>>>
>>> 7 8 9 10 11
>>>
>>> NB. 7 8 9 10 11
>>>
>>> (,3) SequenceIndices 8
>>>
>>> 8 9 10
>>>
>>> NB. 8 9 10
>>>
>>> DropFirstIfPrime=: ((1 {. ]) e. [) }. ]
>>>
>>> 7 11 DropFirstIfPrime 7 8 9 10 11
>>>
>>> 8 9 10 11
>>>
>>> NB. 8 9 10 11
>>>
>>> (i.0) DropFirstIfPrime 8 9 10
>>>
>>> 8 9 10
>>>
>>> NB. 8 9 10
>>>
>>> DropLastIfPrime=: ([: -(_1 {. ]) e. [) }. ]
>>>
>>> (,11)DropLastIfPrime 8 9 10 11
>>>
>>> 8 9 10
>>>
>>> NB. 8 9 10
>>>
>>> (i.0)DropLastIfPrime 8 9 10
>>>
>>> 8 9 10
>>>
>>> f=: 4 : 0
>>>
>>> NB. Find the longest sequence of non-primes in a range
>>>
>>> NB. x and y are the range limits
>>>
>>> primesInRange =. x PrimesInRange y
>>>
>>> NB. Add range limits if they are not primes and then already there
>>>
>>> rangeLimits =. y AddEndRangeIfNotThere x AddStartRangeIfNotThere
>>> primesInRange
>>>
>>> NB. The lengths of the possible sequences, including both sequence limits
>>>
>>> sequenceLengths =. SequenceLengths rangeLimits
>>>
>>> NB. The first element of the longest sequence
>>>
>>> firstInLongestSequence=.sequenceLengths FirstInLongestSequence
>>> rangeLimits
>>>
>>> NB. The longest range including it's both limits
>>>
>>> longestRange =. sequenceLengths SequenceIndices firstInLongestSequence
>>>
>>> NB. Drop the range limits if they are primes
>>>
>>> primesInRange DropLastIfPrime primesInRange DropFirstIfPrime longestRange
>>>
>>> )
>>>
>>> s=: 10 f 100
>>>
>>> s
>>>
>>> 90 91 92 93 94 95 96
>>>
>>> >./90 91 92 93 94 95 96 = s
>>>
>>> 1
>>>
>>> s=: 1 f 2
>>>
>>> >./s = 1
>>>
>>> 1
>>>
>>> s=: 2 f 3
>>>
>>> 0 = $ s
>>>
>>> 1
>>>
>>> s=: 8 f 9
>>>
>>> >./s = 8 9
>>>
>>> 1
>>>
>>> s=: 7 f 8
>>>
>>> >./s = 8
>>>
>>> 1
>>>
>>> s=: 10 f 11
>>>
>>> >./s = 10
>>>
>>> 1
>>>
>>> s=: 7 f 11
>>>
>>> >./s = 8 9 10
>>>
>>> 1
>>>
>>> s=: 200 f 300
>>>
>>> s
>>>
>>> 212 213 214 215 216 217 218 219 220 221 222
>>>
>>> >./0 = 1 p: s
>>>
>>> 1
>>>
>>> 1 = 1 p: _1 + 1 {. s
>>>
>>> 1
>>>
>>> 1 = 1 p: 1 + _1 {. s
>>>
>>> 1
>>>
>>> s=: 2000 f 3000
>>>
>>> s
>>>
>>> 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985
>>> 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998
>>>
>>> >./0 = 1 p: s
>>>
>>> 1
>>>
>>> 1 = 1 p: _1 + 1 {. s
>>>
>>> 1
>>>
>>> 1 = 1 p: 1 + _1 {. s
>>>
>>> 1
>>>
>>> timespacex'200 f 300'
>>>
>>> 0.00132426 18816
>>>
>>>
>>> On 2017-09-17 15:35, Raul Miller wrote:
>>>>
>>>> I was going to look at 200 f 300 and then try timespacex between your
>>>> f and other implementations of f, but I got a value error on
>>>> AddStartRangeIfNotThere
>>>>
>>>> FYI,
>>>>
>>>
>>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
