Hello all <br>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. <br>
<br>import <a href="http://Control.Monad.ST">Control.Monad.ST</a><br>import <a href="http://Data.Array.ST">Data.Array.ST</a><br>import Data.Array.Unboxed<br>import Control.Monad<br><br>prime :: Int -> UArray Int Bool<br>
prime n = runSTUArray $ do<br> arr <- newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool )<br> forM_ ( takeWhile ( \x -> x*x <= n ) [ 2 .. n ] ) $ \i -> do<br> ai <- readArray arr i<br> when ( ai ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j -> do<br>
writeArray arr j False<br><br> return arr <br><br>pList :: UArray Int Bool<br>pList = prime $ 10 ^ 8<br> <br>divPrime :: Int -> Bool <br>divPrime n = all ( \d -> if mod n d == 0 then pList ! ( d + div n d ) else True ) $ [ 1 .. truncate . sqrt . fromIntegral $ n ] <br>
<br><br>main = putStrLn . show . sum $ [ if and [ pList ! i , divPrime . pred $ i ] then pred i else 0 | i <- [ 2 .. 10 ^ 8 ] ]<br><br><br>C++ program which outputs the answer almost instant. <br><br><pre>#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;
        }
</pre><br>Regards <br>Mukesh Tiwari<br>