Thank
Ok people I'm confused, I put this into c++ and it continously cout x at the point i commented. Like it will say 3,3,3,3,3,3,3,3,3,3,3,3,3 a whole bunch then it will say 5,5,5,5,5,5,5,,5,5,5,5,5,5,5,5,5,5 then 7,7,7,7,7,7,7,7,7,7,7,7, and it slows down the process hugely, anyone know why? Should i just try a different compiler?
Also I'm pretty new to coding any tips on how i could make it better besides the fact that i made the array 1 million which is a waste of memory and i could probably find a better way to do it.
#include <iostream>#include <math.h>#include <string>#include <sstream> using namespace std;int w,x,z,result;int * y;bool isprime;int table[1000000];//only odd numbers can be primeint main (){{table[0]=2;w=1;for (x=3, isprime=true ;x<2000000 ;x++,isprime=true){for (y=&table[0];*y<=sqrt (x), isprime==true; y++){if (x%*y!=0&&*y>sqrt (x)){result=(result+x);cout << x <<","; //RIGHT HEREtable[w]=x;w++;}else if (x%*y!=0){isprime=true;}else {isprime=false;} }}while (int a=1)cout << result <<",";} return 0;}
It's been a really long time since I've looked at C code. Because of that I can't suggest much at this moment, I will have to get back to you.
One thing I can suggest that might give you a slight speed up is that in your main loop you're copmaring x%*y!=0 twice. First on line 17 then again for 23. I would change it to something like:
if (x%*y!=0){ if (*y > sqrt(x)){ #stuff } else { isprime = true; }} else { isprime=false;}
Sorry I can't help you more imediately, hopefully I will have more for you in the near future.
My solution :
print sum(prime_sieve(2000000))
Runs under a second ... Find or write a simple implementation of prime_sieve :-)
That's a horrible solution :). Try this:
Try storing the primes you find, then dividing only by them when looking for larger primes, instead of dividing by every number less than the square root.
Thank you for that recommendation. I will implement that suggestion soon.
Not too difficult... my only bug was overflow in the (i*i) calculation.
#include <stdio.h>#include <math.h> #define LIMIT 2000000 int bits[LIMIT/8 + 1]; #define GET_BIT(n) ((bits[n/8]>>(n%8))&1)#define SET_BIT(n) (bits[n/8] |= 1 << (n%8)) int main() { int sqrt_lim = (int)(sqrtf(LIMIT)+1); long long sum=0; for (int i=2; i<LIMIT; i++) { if (! GET_BIT(i)) { // Found a prime/* printf("%d\n", i); */ sum += i; if (i<=sqrt_lim) for (int j=i*i; j<LIMIT; j+=i) { SET_BIT(j); } } } printf("%lld\n", sum);}
This approach is a couple of orders of magnitude faster (nearly three, in fact):
$ gcc euler10.c -std=c99 -ggdb -lm -O2
$ time ./a.out
142913828922
$ gcc euler10.c -std=c99 -ggdb -lm -O2
$ time ./a.out
142913828922
real 0m0.043s
user 0m0.040s
sys 0m0.000s
I have to agree Erik, that is really fast. Very Impressive.
Once I fix the versions to use the Sieve of Erasthones, I'm sure I'll get better times. Something I will try and do soon. :)
PyPy has nice performance for this:
$ time pypy pp.py
142913828922
real 0m5.271s
user 0m5.168s
sys 0m0.088s
CPython 2.7.1:
$ time python pp.py
142913828922
real 0m40.004s
user 0m39.918s
sys 0m0.024s
That is a damn fast improvement. I'm going to have to give PyPy a look. Thanks for sharing your numbers.
If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.