Rosetta Code

Sieve of Eratosthenes: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Rdm (talk | contribs)
6,963 edits
Line 9,626:
{{eff note|J|i.&.(p:inv) }}
 
Implementation:<lang J>sieve=: {{
This problem is a classic example of how J can be used to represent mathematical concepts.
r=. 0#t=. y# j=.1
 
while. y>j=.j+1 do.
J uses x|y ([http://www.jsoftware.com/help/dictionary/d230.htm residue]) to represent the operation of finding the remainder during integer division of y divided by x
if. j{t do.
 
t=. t > y$j{.1
<lang J> 10|13
r=. r, j
3</lang>
end.
 
And x|/y gives us a [http://www.jsoftware.com/help/dictionary/d420.htm table] with all possibilities from x and all possibilities from y.
 
<lang J> 2 3 4 |/ 2 3 4
0 1 0
2 0 1
2 3 0</lang>
 
Meanwhile, |/~y ([http://www.jsoftware.com/help/dictionary/d220v.htm reflex]) copies the right argument and uses it as the left argment.
 
<lang J> |/~ 0 1 2 3 4
0 1 2 3 4
0 0 0 0 0
0 1 0 1 0
0 1 2 0 1
0 1 2 3 0</lang>
 
(Bigger examples might make the patterns more obvious but they also take up more space.)
 
By the way, we can ask J to count out the first N integers for us using i. ([http://www.jsoftware.com/help/dictionary/didot.htm integers]):
 
<lang J> i. 5
0 1 2 3 4</lang>
 
Anyways, the 0s in that last table represent the Sieve of Eratosthenes (in a symbolic or mathematical sense), and we can use = ([http://www.jsoftware.com/help/dictionary/d000.htm equal]) to find them.
 
<lang J> 0=|/~ i.5
1 0 0 0 0
1 1 1 1 1
1 0 1 0 1
1 0 0 1 0
1 0 0 0 1</lang>
 
Now all we need to do is add them up, using / ([http://www.jsoftware.com/help/dictionary/d420.htm insert]) in its single argument role to insert + between each row of that last table.
 
<lang J> +/0=|/~ i.5
5 1 2 2 3</lang>
 
The sieve wants the cases where we have two divisors:
 
<lang J> 2=+/0=|/~ i.5
0 0 1 1 0</lang>
 
And we just want to know the positions of the 1s in that list, which we can find using I. ([http://www.jsoftware.com/help/dictionary/dicapdot.htm indices]):
 
<lang J> I.2=+/0=|/~ i.5
2 3
I.2=+/0=|/~ i.100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</lang>
 
And we might want to express this sentence as a definition of a word that lets us use it with an arbitrary argument. There are a variety of ways of doing this. For example:
 
<lang J>sieve0=: verb def 'I.2=+/0=|/~ i.y'</lang>
 
That said, this fails with an argument of 2 (instead of giving an empty list of the primes smaller than 2, it gives a list with one element: 0). Working through why this is and why this matters can be an informative exercise. But, assuming this matters, we need to add some guard logic to prevent that problem:
 
<lang J>sieve0a=: verb def 'I.(y>2)*2=+/0=|/~ i.y'</lang>
 
Of course, we can also express this in an even more elaborate fashion. The elaboration makes more efficient use of resources for large arguments, at the expense of less efficient use of resources for small arguments:
 
<lang J>sieve1=: 3 : 0
m=. <.%:y
z=. $0
b=. y{.1
while. m>:j=. 1+b i. 0 do.
b=. b+.y$(-j){.1
z=. z,j
end.
}}</lang>
z,1+I.-.b
)</lang>
 
Example:
"Wheels" may be implemented as follows:
 
<lang J>sieve2=: 3 : 0
m=. <.%:y
z=. y (>:#]) 2 3 5 7
b=. 1,}.y$+./(*/z)$&>(-z){.&.>1
while. m>:j=. 1+b i. 0 do.
b=. b+.y$(-j){.1
z=. z,j
end.
z,1+I.-.b
)</lang>
 
The use of<tt> 2 3 5 7 </tt>as wheels provides a
20% time improvement for<tt> n=1000 </tt>and 2% for<tt> n=1e6</tt> but note that sieve2 is still 25 times slower than i.&.(p:inv) for <tt>n=1e6</tt>. Then again, the value of the sieve of eratosthenes was not efficiency but simplicity. So perhaps we should ignore resource consumption issues and instead focus on intermediate results for reasonably sized example problems?
 
<lang J> 0=|/~ i.8
1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 0 0 1 0 0 1 0
1 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1</lang>
 
Columns with two "1" values correspond to prime numbers.
 
'''Alternate Implementation'''
 
If you feel that the intermediate results, above, are not enough "sieve-like" another approach could be:
 
<lang J>sieve=:verb define
seq=: 2+i.y-1 NB. 2 thru y
n=. 2
l=. #seq
whilst. -.seq-:prev do.
prev=. seq
mask=. l{.1-(0{.~n-1),1}.l$n{.1
seq=. seq * mask
n=. {.((n-1)}.seq)-.0
end.
seq -. 0
)</lang>
 
Example use:
 
<lang J> sieve 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</lang>
 
To see intermediate results, let's show them:
 
<lang J>label=:dyad def 'echo x,":y'
 
sieve=:verb define
'seq ' label seq=: 2+i.y-1 NB. 2 thru y
'n ' label n=. 2
'l ' label l=. #seq
whilst. -.seq-:prev do.
prev=. seq
'mask ' label mask=. l{.1-(0{.~n-1),1}.l$n{.1
'seq ' label seq=. seq * mask
'n ' label n=. {.((n-1)}.seq)-.0
end.
seq -. 0
)
 
seq 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
n 2
l 59
mask 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
seq 2 3 0 5 0 7 0 9 0 11 0 13 0 15 0 17 0 19 0 21 0 23 0 25 0 27 0 29 0 31 0 33 0 35 0 37 0 39 0 41 0 43 0 45 0 47 0 49 0 51 0 53 0 55 0 57 0 59 0
n 3
mask 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
seq 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 25 0 0 0 29 0 31 0 0 0 35 0 37 0 0 0 41 0 43 0 0 0 47 0 49 0 0 0 53 0 55 0 0 0 59 0
n 5
mask 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
seq 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 49 0 0 0 53 0 0 0 0 0 59 0
n 7
mask 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1
seq 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 0 0 0 0 53 0 0 0 0 0 59 0
n 11
mask 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
seq 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 0 0 0 0 53 0 0 0 0 0 59 0
n 13
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59</lang>
 
Another variation on this theme would be:
 
<lang J>
sieve=: monad define
seq=. 2+i.y-1 NB. integers 2 thru y
n=. 1
sl=. #seq NB. seq length
whilst. -.seq-:prev do.
prev=. seq
n=. 1+n+ 1 i.~ *(n-1)}. seq NB. next n, using Drop (}.) and Index of (x i. y)
ind0=. 2-~+:n NB. start index
inds=. ind0+n*i.>.(sl-ind0)%n NB. all indices
seq=. 0 inds} seq NB. Amend (}) seq with 0s at inds
end.
seq -. 0 NB. remove all 0s
)
</lang>
 
Intermediate results for this variant are left as an exercise for the reader.
 
=={{header|Janet}}==
Retrieved from "https://rosettacode.org/wiki/Sieve_of_Eratosthenes"