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.

Advertisements

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. If u search in google by “Himesh Reshamiya Club”…U may get lots of results…
    Himesh may have tried it once and…
    I think bcoz of such clubs only Himesh may b feeling that he is very famous and may b that inspires him to sing more and more…
    but i guess he doesn’t read after “Himesh Reshamiya”…which is “HATE CLUB”
    Himeshbhai…Akhu Vancho. :D

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s