# Project Euler

I got this website link from Sweetesh. And all the problems mentioned in this website are mostly one liners. I like small problem definition and hence started solving them. The problem statement is pretty small, and the solution problem will also be pretty small but the run time that the solution takes will be huge. And here comes the technique of optimization which can save your time to test your solution. I also learned that even if python is rocking language, but it fails when it comes to speed, and nobody can beat C i suppose.

I was solving a problem of finding the sum of all prime numbers less than 2 million. It took less than 1 minute in C, and in python, I was never able to see the answer. I will post both the codes tomorrow morning. I’ve done little optimization in finding the prime numbers :P

Edit :
=====
So the little optimization in finding prime number: Starting with 3, increment the number by 2 (as even number will never be prime). Maintain a list of already found prime numbers. Initialize this list with 2 (as we are starting with 3, prime number before 3 is 2). For each iteration (i.e. 3,5,7,9,11,13,15..) just do modulo operation with the numbers present in the prime_list, if it results in zero, it means it is not prime. Else, add it that number into the list of prime number. Here is the code in C:

```#include <stdio.h>
#include <malloc.h>

unsigned int limit = 2*1000*1000;

int main()
{
unsigned long long *plist;
plist = (unsigned long long*)calloc(limit, sizeof(unsigned long long));
if (plist) {
unsigned long long i, j, idx = 1;
unsigned long long sum = 2;
int flag;
plist[0] = 2;
for (i = 3; i < limit; i+=2) {
flag = 0;
for (j = 0; j < idx; j++) {
if (i % plist[j] == 0) {
flag = 1;
break;
}
}
if (flag == 0) {
plist[idx] = i;
idx++;
sum += i;
}
}
printf("sum = %llu, idx=%llu\n", sum, idx);
free(plist);
}
return 0;
}
```

And here are the two python versions:

Version 1: It has the prime list preallocated, so that no need to call .append() on list every time we find a prime number. This MAY help in optimizing.

```#!/usr/bin/python
ans=10;
limit = 2*1000*1000;
plist=[0]*limit
plist[0:2] = [2,3,5];
counter = 3;
j = 0;
for i in range(6,limit):
flag = 0;
while j < counter:
if (i%plist[j] == 0):
flag = 1;
break;
if (flag == 0):
ans = ans+i;
plist[counter]=i;
counter = counter+1
j = j+1;
print ans
```

Version 2: This will append all the prime numbers dynamically (as found), which may be slower, but the code is very less.

```#!/usr/bin/python
ans=10;
limit = 2*1000*1000;
plist[0:2] = [2,3,5];
for i in range(6,limit):
flag = 0;
for j in plist:
if (i%j == 0):
flag = 1;
break;
if (flag == 0):
ans = ans+i;
plist.append(i);
print ans

```

Anyways, I have not got the results with the above python code, as it is very time consuming. Anyone may want to optimize these codes.

## 5 thoughts on “Project Euler”

1. be you should say he is unpopular amongst ghosts!
even the ghosts dont like anybody singing his songs….thats y they enter the person who is singing..
himesh should go and sing his song near the SMASHAN GRUH in AMBAVADI
hehe

2. Where did u get this news from???
“SANDESH” OR “GUJARAT SAMACHAR”??

3. gujarat samachar (obviosly.. in jenish style) :D :D