0

For project euler Problem 10, we are supposed to add all primes but that is taking my computer years to do it. Need a more efficient algorithm! Heres my present C code:

#include <stdio.h>

int main(void) 
{
int i, j, flag, sum=0;
for(i=3; i< 2000000; i = i + 2)
{
  flag=0;
  for(j=3; j<=i/2; j = j + 2)
  {
    if(i%j==0)
    {
      flag=1;
      break;
    }
  }
  if(flag==0)
    sum += i;
 }
printf ("%i", sum + 2);
}
Cœur
  • 37,241
  • 25
  • 195
  • 267
user3497878
  • 15
  • 3
  • 17
    Hint: [Sieve of Eratosthnenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). Others: Please don't answer this question. It's an easy question to answer, but the point of Project Euler is to learn something. If you want to provide an actual answer, do it in the spirit of Project Euler, and point the OP in the right direction, don't give him the answer in terms of code (changes). – Lasse V. Karlsen Apr 05 '14 at 19:00
  • 1
    See comment above. As a side note, you only need to check for possible factors up to the square root, since at least one of the factors of a composite number will be less than or equal to the square root. – user3386109 Apr 05 '14 at 19:04
  • @LasseV.Karlsen agreed, related discussion [here](http://math.stackexchange.com/a/720174/77151) – TooTone Apr 05 '14 at 19:07
  • Will need more help, HOW TO USE THIS ??? – user3497878 Apr 05 '14 at 19:09
  • Take a look at this: http://stackoverflow.com/questions/7921456/sieve-of-eratosthenes – Lasse V. Karlsen Apr 05 '14 at 19:13
  • Sorry, but now whats happening is quite odd. Though the present program is correct and takes around a minute to solve the problem, and the obtained answer is 1179908154, which is wrong according to the website, WHY IS THIS SO ? is there an error in my present script, @LasseV.Karlsen ??? – user3497878 Apr 06 '14 at 14:53
  • 1
    Though its fuctioning correctly for prime numbers under 10, but when under 2 million, the output is wrong. @TooTone and #LasseV.Karlsen – user3497878 Apr 06 '14 at 15:01
  • Overflow? Try switching to Int64. – Lasse V. Karlsen Apr 06 '14 at 17:23
  • Really, you are asking a question that has been answered again and again and again. – gnasher729 Jan 22 '15 at 10:36

1 Answers1

0

Here is a slight improvement to your procedure, while keeping the same algorithm for testing primality:

  • Set the sum variable to the sum of the first two primes (i.e., 2+3 = 5)
  • Start from 5, and test only numbers that are adjacent to multiples of 6
  • For each number, test it only with divisors that are adjacent to multiples of 6
  • For each number, test it only with divisors between 5 and the square root of the number

Please note that this implementation improves the performance of the algorithm but not the time-complexity of the algorithm, and that there are more efficient methods for testing primality.

int i, j, iplus, jplus, flag, iroot, sum = 2+3;

int iroot  = (int)ceil(sqrt((float)5));
int square = iroot*iroot;

for (i=5, iplus=2; i<2000000; i+=iplus, iplus=4-iplus)
{
    flag = 0;
    if (square < i)
    {
        iroot++;
        square = iroot*iroot;
        // instead of calculating the square root of the number every time,
        // calculate it at the beginning, and increment it only when needed
    }
    for (j=5, jplus=2; j<=iroot; j+=jplus, jplus=4-jplus)
    {
        if (i%j == 0)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        sum += i;
}

printf("%i", sum);
barak manos
  • 29,648
  • 10
  • 62
  • 114
  • If you want to take this and run with it, until its logical conclusion, try [this code](http://stackoverflow.com/a/3941956/153285). – Potatoswatter Apr 05 '14 at 19:28