Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Problem found in first Erlang example.
| (7 intermediate revisions by 4 users not shown) | |||
Line 274:
::::: but those versions are inefficient anyway. Plus, the proper way to test is to run a compiled, standalone executable, where even <code>primes :: [Int]</code> is garbage collected and runs in near constant memory; while if playing at GHCi prompt, depending on a version, I've seen even <code>primes :: () -> [Int]</code> memoized. But here I thought the aim is to showcase a language not even to (practicing) newbies (there are plenty more other resources for those), but to people even totally unfamiliar with it, just to glance over (but the snippets are still runnable of course). So for me, clarity was the utmost goal. [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 12:06, 12 April 2015 (UTC)
==Problem found in first Erlang example.==
A note. This code bugs out on
<pre>
3> erato:primes_upto(100).
** exception error: no true branch found when evaluating an if expression
in function lists:seq/3 (lists.erl, line 249)
in call from erato:find_prime/3 (erato.erl, line 18)
in call from lists:foldl/3 (lists.erl, line 1248)
in call from erato:primes_upto/1 (erato.erl, line 10)
</pre>
Problem found by user Poetaster . I just moved the report here. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 06:53, 19 September 2015 (UTC)
corrected version:
<lang Erlang>
-module( sieve_of_eratoshenes ).
-export( [primes_upto/1] ).
primes_upto( N ) ->
Ns = lists:seq( 2, N ),
Dict = dict:from_list( [{X, potential_prime} || X <- Ns] ),
{Upto_sqrt_ns, _T} = lists:split( erlang:round(math:sqrt(N)), Ns ),
{N, Prime_dict} = lists:foldl( fun find_prime/2, {N, Dict}, Upto_sqrt_ns ),
lists:sort( dict:fetch_keys(Prime_dict) ).
find_prime( N, {Max, Dict} ) -> find_prime( dict:find(N, Dict), N, {Max, Dict} ).
find_prime( error, _N, Acc ) -> Acc;
find_prime( {ok, _Value}, N, {Max, Dict} ) when Max > N*N ->
{Max, lists:foldl( fun dict:erase/2, Dict, lists:seq(N*N, Max, N))};
find_prime( {ok, _Value}, _, R) -> R.
</lang>
== R code error ==
In the R code, the inner loop does not start at the square of the prime just found. The code tries to change the index of the loop using last.prime.
for(i in last.prime:floor(sqrt(n)))
{
primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE
last.prime <- last.prime + min(which(primes[(last.prime+1):n]))
}
which(primes)
}
However from R in the help function - The ‘seq’ in a ‘for’ loop is evaluated at the start of the loop;changing it subsequently does not affect the loop. If ‘seq’ has
length zero the body of the loop is skipped. Otherwise the variable ‘var’ is assigned in turn the value of each element of‘seq’. You can assign to ‘var’ within the body of the loop, but this will not affect the next iteration. When the loop terminates,
‘var’ remains as a variable containing its latest value.
If you wish to change the loop you can use a while or repeat if written below.
sieveOfEratosthenes<-function(n){
list<-2:n #list of numbers 2:n
A<-rep(TRUE,(n)) # Vector of true - if true at end prime
i<-2 #index at 2 first
repeat{
if(A[i]==TRUE)
{
A[seq(i**2,n,i)]=FALSE
}
if(i>sqrt(n))
{
break
}else{
i<-i+1
}
}
return(list[A[-1]]) #remove 1
}
:Corrected. Some oddities in your own program: once you have computed i^2, no need to compute sqrt(n), just compare i^2 and n. Also, no need for 'list', use the 'which' function. You may replace 'break' with 'return' and 'repeat' with a 'for' loop since you are incrementing the index 'i' at the end of each loop. Last, but not least, your function fails for all n < 9, probably due to a nasty bug you didn't investigate: 'seq(a, b)' is not empty when a > b. [[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 12:16, 12 December 2016 (UTC)
== Pari/GP script ==
The first script uses "forprime(p=2,sqrt(lim)" which seems contrary to the task assignment.[[User:Billymacc|Billymacc]] ([[User talk:Billymacc|talk]]) 03:01, 4 May 2021 (UTC)
| |||