May I suggest you try a non-ST solution first (e.g. using Data.IntMap) first (assuming an auxiliary data-structure is required)?
Also, I'm not sure if the logic in the two versions is the same: I'm not sure about how you handle the boolean aspect in C++, but you have a third for-loop there that doesn't seem to correspond to anything in the Haskell version. On 8 November 2011 22:50, mukesh tiwari <mukeshtiwari.ii...@gmail.com> wrote: > I am not sure about Int overflow. There is no case of Int overflow in prime > , pList and divPrime function however lets assuming Int overflow in main but > then still answer should be outputted. > > Regards > Mukesh Tiwari > > On Tue, Nov 8, 2011 at 5:08 PM, Lyndon Maydwell <maydw...@gmail.com> wrote: >> >> Could Int be overflowing? >> >> On Tue, Nov 8, 2011 at 7:21 PM, mukesh tiwari >> <mukeshtiwari.ii...@gmail.com> wrote: >> > Hello all >> > Being a Haskell enthusiastic , first I tried to solve this problem in >> > Haskell but it running for almost 10 minutes on my computer but not >> > getting >> > the answer. A similar C++ program outputs the answer almost instant so >> > could >> > some one please tell me how to improve this Haskell program. >> > >> > import Control.Monad.ST >> > import Data.Array.ST >> > import Data.Array.Unboxed >> > import Control.Monad >> > >> > prime :: Int -> UArray Int Bool >> > prime n = runSTUArray $ do >> > arr <- newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool ) >> > forM_ ( takeWhile ( \x -> x*x <= n ) [ 2 .. n ] ) $ \i -> do >> > ai <- readArray arr i >> > when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j -> do >> > writeArray arr j False >> > >> > return arr >> > >> > pList :: UArray Int Bool >> > pList = prime $ 10 ^ 8 >> > >> > divPrime :: Int -> Bool >> > divPrime n = all ( \d -> if mod n d == 0 then pList ! ( d + div n d ) >> > else >> > True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ] >> > >> > >> > main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $ >> > i ] >> > then pred i else 0 | i <- [ 2 .. 10 ^ 8 ] ] >> > >> > >> > C++ program which outputs the answer almost instant. >> > >> > #include<cstdio> >> > #include<iostream> >> > #include<vector> >> > #define Lim 100000001 >> > using namespace std; >> > >> > bool prime [Lim]; >> > vector<int> v ; >> > >> > void isPrime () >> > { >> > for( int i = 2 ; i * i <= Lim ; i++) >> > if ( !prime [i]) for ( int j = i * i ; j <= Lim ; j += i >> > ) prime [j] = 1 >> > ; >> > >> > for( int i = 2 ; i <= Lim ; i++) if ( ! prime[i] ) >> > v.push_back( i ) ; >> > //cout<<v.size()<<endl; >> > //for(int i=0;i<10;i++) cout<<v[i]<<" ";cout<<endl; >> > >> > } >> > >> > int main() >> > { >> > isPrime(); >> > int n = v.size(); >> > long long sum = 0; >> > for(int i = 0 ; i < n ; i ++) >> > { >> > int k = v[i]-1; >> > bool f = 0; >> > for(int i = 1 ; i*i<= k ; i++) >> > if ( k % i == 0 && prime[ i + ( k / i ) ] >> > ) { f=1 ; break ; } >> > >> > if ( !f ) sum += k; >> > } >> > cout<<sum<<endl; >> > } >> > >> > Regards >> > Mukesh Tiwari >> > >> > _______________________________________________ >> > Haskell-Cafe mailing list >> > Haskell-Cafe@haskell.org >> > http://www.haskell.org/mailman/listinfo/haskell-cafe >> > >> > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe