[Jprogramming] Quora Challenge

[Erling Hellenäs]

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,
>>>
>>
>