My Weblog

Blog about programming and math

Project Euler 357

Project Euler 357 is easy one. I was trying to solve problem 356 and finally ended up with solving easy problem. Nothing new just sieve of eratosthenes and couple of constraints.
Edit: Finally wrote a Haskell solution. See more discussion on Haskell-Cafe. Compile this code with ghc –make -O2 filename.hs

import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 
import Control.Monad 
import Data.List


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 ( fromIntegral . pred $ i ) else 0 | i <- [ 2 .. 10 ^ 8 ] ] :: [ Integer ] ) 
#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;
	}
Advertisements

November 7, 2011 - Posted by | Programming | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: