Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Problem found in first Erlang example.
| (6 intermediate revisions by 3 users not shown) | |||
Line 287:
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)
| |||