Project Euler #10: Summation of primes

Sort by

recency

|

216 Discussions

|

  • + 0 comments

    Did it with DIctionary Generated primes initially and added their sum.

    def generate_primes(n: int) -> {}:
        is_prime = [True] * (n+1)
        is_prime[0] = is_prime[1] = False
        
        i = 2
        while i*i < n+1:
            if is_prime[i]:
                for j in range(i*i, n+1, i):
                    is_prime[j] = False
            i += 1
        
        primes = {}
        primes[2] = 2
        j = 2
        for i in range(3, n+1):
            if is_prime[i]:
                primes[i] = i + primes[j]
                j = i
        return primes
            
        
    primes = generate_primes(10000000)
    
    def solve(n: int) -> int:
        if n == 0:
            return 0
        
        i = n
        while i > 0:
            if i in primes:
                return primes[i]
            i -= 1
        return 0
    
  • + 0 comments

    t = int(input().strip()) for a0 in range(t): n = int(input().strip()) l=[2] for i in range(3,n+1,2): r=1 for j in l: if i%j==0: r=0 break if r: l.append(i)
    print(sum(l))

    its stilll showing timeout, how can i optimize it further??

  • + 1 comment

    My script in python was as follows:

    /* ---------------------------------------------------------------- *
     * IMPORTS
     * ---------------------------------------------------------------- */
     
    use std::io;
    use std::io::BufRead;
    use std::collections::HashMap;
    
    /* ---------------------------------------------------------------- *
     * MAIN
     * ---------------------------------------------------------------- */
    
    fn main() {
        let stdin = io::stdin();
        let mut stdin_iterator = stdin.lock().lines();
    
        let t = stdin_iterator
            .next()
            .unwrap().unwrap()
            .trim()
            .parse::<i32>()
            .unwrap();
    
        let mut numbers = Vec::<i32>::new();
        let mut n_max: i32 = 0;
        for _ in 0..t {
            let n: i32 = stdin_iterator
                .next()
                .unwrap().unwrap()
                .trim()
                .parse::<i32>()
                .unwrap();
            if n > n_max {
                n_max = n;
            }
            numbers.push(n);
        }
    
        let primes = get_primes(n_max);
        let sums = compute_aggregates(&numbers, n_max, &primes);
        for n in numbers.iter() {
            if let Some(s) = sums.get(n) {
                println!("{:?}", s);
            }
        }
    }
    
    /* ---------------------------------------------------------------- *
     * HELPER METHODS
     * ---------------------------------------------------------------- */
    
    fn get_primes(t: i32) -> Vec<i32> {
        let mut map = HashMap::<i32, bool>::new();
        let mut result = Vec::<i32>::new();
        for p in 2..=t {
            if map.get(&p) != Some(&false) {
                result.push(p);
                (2*p..=t).step_by(p as usize).for_each(|k| {
                    map.entry(k).or_insert(false);
                });
            }
        }
        return result;
    }
    
    fn compute_aggregates(
        numbers: &Vec<i32>,
        n_max: i32,
        primes: &Vec<i32>,
    ) -> HashMap::<i32, i32> {
        let mut primes_ = primes.clone();
        primes_.push(n_max + 1);
        let mut sum: i32 = 0;
        let mut sums = HashMap::<i32, i32>::new();
        let mut numbers_sorted = numbers.clone();
        numbers_sorted.sort();
    
        for n in numbers_sorted {
            let mut k_final: usize = 0;
            for (index, &p) in primes_.iter().enumerate() {
                k_final = index;
                if p > n {
                    break;
                }
                sum += p;
            }
            primes_ = primes_[k_final..].to_vec();
            sums.entry(n).or_insert(sum);
        }
    
        return sums;
    }
    

    It passed all tests. I implemented an equivalent approach in Rust but received timeout errors for 6 and 7. Any ideas?

  • + 0 comments

    Haskell

    import Control.Applicative
    import Control.Monad
    import System.IO
    import Data.List
    
    primes = 2 : [i | i <- [3..1000000],  
                  and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) primes]]
                 
    main :: IO ()
    main = do
        t_temp <- getLine
        let t = read t_temp :: Int
        forM_ [1..t] $ \a0  -> do
            n_temp <- getLine
            let n = read n_temp :: Int
            let primesToInput = filter (<= n) primes
            print (sum primesToInput)
    
  • + 0 comments

    include

    include

    include

    using namespace std; bool isprime(long number){ if((number != 2 && number != 3 && number != 5) && (number % 2 == 0 || number % 3 == 0 || number % 5==0))

    return false;
    
    for(long i =2; i*i <= number; i++){
        if(number % i == 0)
        return false;
    }
    return true;
    

    }

    int main(){ vector primes; for(long i = 2; i<1000000; i++){ if (isprime(i)) primes.push_back(i); }

    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        long sum = 0;
    
        for(long num : primes){
            if(num >n)
            break;
            sum += num;
        }
        cout << sum << endl;
    }
    
    return 0;
    

    }