[Haskell-cafe] Project Euler Problem 357 in Haskell

[Ryan Yates]

If I compile with optimizations:

ghc --make -O3 primes.hs

I get an answer that is off by one from the C++ program in a few seconds.


On Tue, Nov 8, 2011 at 7:46 AM, mukesh tiwari
<mukeshtiwari.iiitm at gmail.com> wrote:
> In that loop , I  am collecting all the primes in vector how ever I changed
> the c++ code and  now it resembles to Haskell code. This code  still gives
> the answer within a second.
>
> #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 < Lim ; i ++)
>          if ( ! prime [i])
>          {
>             int k = 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
>
> On Tue, Nov 8, 2011 at 6:03 PM, Ivan Lazar Miljenovic
> <ivan.miljenovic at gmail.com> wrote:
>>
>> On 8 November 2011 23:29, mukesh tiwari <mukeshtiwari.iiitm at gmail.com>
>> wrote:
>> >> 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.
>> >>
>> > Which  loop ?
>>
>> for( int i = 2 ; i <= Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
>>
>> --
>> Ivan Lazar Miljenovic
>> Ivan.Miljenovic at gmail.com
>> IvanMiljenovic.wordpress.com
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>