'Summation of primes' takes too long

Question

I don't know why this takes forever for big numbers I'm trying to solve Problem 10 in Project Euler (https://projecteuler.net/problem=10). Can someone help me please?

It finds the first prime number and crosses all its factors, Then moves on to the next prime number and so on.

long sum=0;
        int howmanyChecked = 1;
        int target = 1000000;
        int index = -1;
        List<int> numbers = new List<int>(target);
        List<bool> Isprime = new List<bool>(target);
        for(int i=2;i<=target;i++)
        {
            numbers.Add(i);
            Isprime.Add(true);
        }
        while (1 > 0)
        {
            index = Isprime.IndexOf(true, index + 1);

            int Selected = numbers[index];
            howmanyChecked++;


            sum += Selected;
            //Console.WriteLine($"selected prime number is {Selected}");
            //int startfrom =numbers.IndexOf(Selected * Selected);
            if (Selected >= target / 2)
            {
                Console.WriteLine("ss");
                for(int i=index+1;i<target-1;i++)

                {
                    if(Isprime[i]==true)
                    {
                        Console.WriteLine(numbers[i].ToString());
                        sum += numbers[i];
                    }
                }
                Console.WriteLine($"the sum of all prime nubers below {target} is {sum} tap to continue");
                Console.ReadLine();
                break;


            }
            else
            {
                for (int i = Selected; i * Selected <= target; i++)
                {
                    int k = numbers.IndexOf(i * Selected);
                    if (k == -1)
                        break;
                    if (Isprime[k] == true)
                    {
                        Isprime[numbers.IndexOf(i * Selected)] = false;
                        howmanyChecked++;
                        //Console.WriteLine($"Checked number is {Selected * i} and we have counted {howmanyChecked} numbers");
                    }



                }
            }
            if (howmanyChecked == target || index==target)
                break;
            
        }


        Console.ReadLine();

You don't need two lists. Usually you'd use an array of `bool` where the index is the number and you set the value to indicate if the number is prime. — juharr, Jan 01 '21 at 04:03

score 2 · Accepted Answer · answered Jan 01 '21 at 05:51

Apply some straightforward optimizations:

list numbers should not be used because each number can be calculated based on an index
simplified initialization of Isprime.

For 1'000'000 got:

the sum of all prime numbers below 1000000 is 37548466742 tap to continue

long sum = 0;
int howmanyChecked = 1;
int target = 1000000;
int index = -1;
var Isprime = Enumerable.Repeat(true, target).ToArray();

while (1 > 0)
{
    index = Array.IndexOf(Isprime, true, index + 1);

    int Selected = index + 2;
    howmanyChecked++;


    sum += Selected;
    //Console.WriteLine($"selected prime number is {Selected}");
    //int startfrom =numbers.IndexOf(Selected * Selected);
    if (Selected >= target / 2)
    {
        Console.WriteLine("ss");
        for (int i = index + 1; i < target - 1; i++)

        {
            if (Isprime[i] == true)
            {
                Console.WriteLine(i + 2);
                sum += i + 2;
            }
        }
        Console.WriteLine($"the sum of all prime nubers below {target} is {sum} tap to continue");
        Console.ReadLine();
        break;
    }
    else
    {
        for (int i = Selected; i * Selected <= target; i++)
        {
            int k = i * Selected - 2;
            if (k < 0)
                break;
            if (Isprime[k] == true)
            {
                Isprime[k] = false;
                howmanyChecked++;
                //Console.WriteLine($"Checked number is {Selected * i} and we have counted {howmanyChecked} numbers");
            }
        }
    }
    if (howmanyChecked == target || index == target)
        break;

}

Console.ReadLine();

the task is sum of all primes below `2000000` which is `142913828922` — Spektre, Jan 01 '21 at 09:37

Spektre · Answer 2 · 2021-01-01T10:04:19.167

Do SoE (Sieve of Eratosthenes) up to n=2000000 in case you want to be memory efficient 2000000/16 = 62500 Bytes as you need just one bit per odd number). You can do the sum while filling SoE.

Your description is a SoE but you got too much code for a SoE ... my simple SoE solution for this is just 11 lines of formatted C++ code where half of it is variables declaration:

const DWORD N=2000000;                      // ~ 36 ms
const DWORD M=N>>1;                         // store only odd values from 3,5,7,...
char p[M];                                  // p[i] ->  is 1+i+i prime? (factors map)
DWORD i,j,k,ss=0,n=0x10000000-N;
uint<2> s=2;
p[0]=0; for (i=1;i<M;i++) p[i]=1;
for(i=3,j=i>>1;i<N;i+=2,j++)
    {
    if (p[j]==1) { ss+=i; if (ss>=n) { s+=DWORD(ss); ss=0; }}
    for(k=i+j;k<M;k+=i) p[k]=0;
    } s+=DWORD(ss);
// s holds the answer 142913828922

where DWORD is unsigned 32bit int and uint<2> is 64bit unsigned int (as I am still on 32bit compiler that is why I do the sum so weirdly). As you can see you got maybe 3 times more code than necessary.

Using IsPrime without memoization is too slow but even with memoization can never beat SoE. see:

Prime numbers by Eratosthenes quicker sequential than concurrently?

btw. I got my Euler projects in single app where I do SoE up to 10^7 which creates a list of all primes up to 10^7 this takes 130 ms on my pretty old PC and that is then used for all the Euler problems related to primes (which speeds them up so the first 40 problems is finished below 1sec) which for this case (different solution code) takes 0.7 ms.

To avoid overflows sum on 64 bit arithmetics.

Also using dynamic lists without pre-allocation is slow. You do not need them anyway.

score -1 · Answer 3 · answered Jan 01 '21 at 10:27

Try with this:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

int main()
{
    int  n,i,i1,imax;
    long sumprime;
    bool *prime5mod6,*prime1mod6;

    n=2000000;
    
    imax=(n-n%6)/6+1;
    prime5mod6 = (bool *) calloc(imax+1,sizeof(bool));
    prime1mod6 = (bool *) calloc(imax+1,sizeof(bool));
    
    sumprime=5;         
    for(i=1;(6*i-1)*(6*i-1)<=n;i++){
        if(prime5mod6[i]==false){
             sumprime=sumprime+6*i-1;
             for(i1=6*i*i;i1 <= imax+2*i;i1+=(6*i-1)){
                if(i1<=imax)
                   prime5mod6[i1]=true;
                prime1mod6[i1-2*i]=true;        
             }
        }
        if(prime1mod6[i]==false){
             sumprime=sumprime+6*i+1;
             for(i1 = 6*i*i;i1<=imax;i1+=(6*i+1)){
                prime5mod6[i1]=true;
                if(i1<=imax-2*i)
                    prime1mod6[i1+2*i]=true;        
             }
        }
    }

    for(i1=i;i1<=imax-1;i1++){
        if(prime5mod6[i1]==false)
             sumprime=sumprime+6*i1-1;
        if(prime1mod6[i1]==false)
             sumprime=sumprime+6*i1+1;
    }
    if(prime5mod6[imax]==false && n%6==5)
             sumprime=sumprime+6*imax-1;
    if(prime1mod6[imax-1]==false && n%6==0)
             sumprime=sumprime-(6*(imax-1)+1);

    printf("\nPrime sum: %ld",sumprime);
    free(prime5mod6);
    free(prime1mod6);
    return 0;
}

'Summation of primes' takes too long

3 Answers3