next »

[Ashkin]

... Wait, you're supposed to program functions to solve these problems? No wonder trying to solve the first one in my head was so hard.
Anyway, just registered:
17340617327248_4330b9cda8e862e6254c2c02d799836f
I'll probably be terrible at this, but hey, it's worth a try.

[Dacke]

Hehe, yeah, that's the whole point

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

(But the first problem can be solved in your head, if you know the right formula(s). When you complete the problem you'll get access to a secret forum thread, where you can learn how )

But anyway, glad to have you aboard!

[imaginationac]

Here's my key:

50667612327256_708fa68d07e1623bed1580aea227b9a0

[Ashkin]

Is problem 3 supposed to take up a lot of CPU and take forever (stupid default script timeout), or am I just doing something terribly, terribly wrong?

[mokesmoe]

If it's taking forever you are doing something at least slightly wrong.

Are you stopping the script at some point? You make it sound like you aren't.

[Ashkin]

If it's taking forever you are doing something at least slightly wrong.

Are you stopping the script at some point? You make it sound like you aren't.

Here's my code. FIX IT.

Code:

var largestnum:int;
for (var num:int = 1; num < 600851475143 / 2; num++)
{
	for (var i:int = 3; i < Math.sqrt(num); i++)
	{
		if (600851475143 % num != 0) break;
		if (i == (Math.sqrt(num) - 1)) trace(num);
		if (num % i == 0) break;
	}
}
			trace(largestnum);

I had a (I think) stupider approach before, but even this times out (I hate FlashDevelop sometimes.)

[Moczan]

FlashDevelop is just an IDE, you can't hate it for timing out cause that's FlashPlayer's work  Also your code doesn't do anything. You should look up integer factorization to solve this problem.

[Ashkin]

I already fixed it. On to problem 4 now.
Man, I feel stupid.

[mokesmoe]

I misunderstood timing out. I though you meant you letting it run until it timed out, not that it timed out before finishing.

Anyways, I used a different method of solving it than checking each value:

I just kept dividing it by numbers, staring with two and going up by one whenever when it isn't divisible. The final number I use when the starting number reaches one is the largest prime factor.

Basically I take out prime factors one at a time until I've reached the last one.


Also nothing seems to ever change largestnum in your code and your if statement for trace(num) seems like it would never fire. (Unless sqrt returns an int.)

EDIT: ninja'd but oh well.

[Toeofdoom]

I haven't done any for a while, but this is mine:


and a friend key: 10848697140136_72f6d8fa7b0732794b402f3dbeb406e6
I might have to try some more soon.

I managed to get in the first 30 for problem #345, but it was the easiest of 5 that came out at the same time. It's interesting seeing all the tricks you build up over time.

[Dacke]

No problem, if done right, should take more than a minute to run on a slow computer. That is one of the design goal of all the problems! So if a problem takes too long, just kill the program and work some more on your code. (But if you don't feel like optimizing, there is nothing wrong with running a single problem for ~5 minutes)

Generating primes and prime factorization are very important concepts. There are a few simple tricks you can use. Like increasing step size to two, so that you only check odd numbers. Or only checking up to the square root of the number you are trying to divide (that works for your approach as well mokesmoe, as the remainder will be a prime if it is >1). Or do what I do and use the simplest prime sieve: the Sieve of Eratosthenes: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Toeofdoom: Added. I'm glad I'm not the "leader" anymore! I have been completely unable to solve the high-numbered problems so I'm going for a linear approach.

[Ashkin]

Welp: paste, BlademasterBobo and I are stuck on problem 10 (I'm stuck, they're helping.)
Here's the code I'm currently using:

Code:

		/**
		 *	This takes an array of numbers and adds them all together.
		 * @param	_terms	The numbers you want to add together
		 * @return	The sum of all of the terms
		 */
		public function sumOfTerms(terms:Array):Number
		{
			var num:int = 0;
			for (var i:int = 0; i < terms.length; i++)
			{
				num += terms[i];
			}
			return(num);
		}

		/**
		 * Takes a number, returns true if it is a prime number.
		 * @param	num	The number to be checked
		 * @return	A boolean value, true if the number is prime
		 */
		public function isPrime(num:Number):Boolean
		{
			if (num < 2) return(false);
			if (num == 2) return(true);
			var sqrt:int = Math.sqrt(num);
			for (var i:int = 0; i < _primes.length; i++)
			{
				if (_primes[i] > sqrt) break;
				if (num % _primes[i] == 0) return(false);
			}
			return(true);
		}

		/**
		 * 	Returns an array of prime numbers, each below the maximum.
		 * @param	max	The maximum which a prime number may not exceed
		 * @return	An array full of prime numbers, each less than the maximum
		 */
		public function primes(max:Number):Array
		{
			var array:Array = new Array();
			
			for (var i:int = 0; i > -1; i++)
			{
				if (i >= max) break;
				if (isPrime(i))
				{
					_primes.push(i);
					array.push(i);
				}
			}
			
			return(array);
		}

//The code I execute
trace(sumOfTerms(primes(2000000));

It makes it to the end fine, but the answer (1179908154) is apparently wrong. We're thinking maybe the answer is just too big for AS3's Number or something.

[Dacke]

I think you'll benefit the most from some debugging advice!

Start by testing if your overflow theory is correct (it may very well be, I don't know). A simple way of doing this is to add a test to sumOfTerms.

Code:

public function sumOfTerms(terms:Array):Number {
   var previous:int = 0;
   var num:int = 0;
   for (var i:int = 0; i < terms.length; i++) {
      previous = num;
      num += terms[i];
      if (num<previous) {
         trace("overflow!");
      }
   }
   return(num);
}

edit1: Note that this test could fail if the term added is so big that num overflows and comes all the way around. But I don't think that can happen here.

edit2: I'm not sure if AS3 overflow works like that. But it is probably safe to assume that it either overflows to negative numbers (C-style) or throws an exception (Java-style)

[BlueSweatshirt]

Or look it up in the documentation.

http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/Number.html#MAX_VALUE

MAX_VALUE   Constant
public static const MAX_VALUE:Number
Language Version:    ActionScript 3.0
Runtime Versions:    AIR 1.0, Flash Player 9, Flash Lite 4
The largest representable number (double-precision IEEE-754). This number is approximately 1.79e+308.

(or you could have just traced in to the debug console in code)

You're definitely not hitting the limit.

[Dacke]

Wow, 1.79*10³⁰⁸, that's a big number.
Yeah, you're not hitting the limit. Generally I think it is good to do manual tests when things are bugging out, but there is no way you'd be able to hit that max value.

Okay, another thing you can test:
Run it for a much smaller number. In the problem description they show you the expected result of summing all primes below 10. Does your code work for that?

If it does, try it for a slightly bigger number that you can still verify manually. For example, print the prime numbers you get under 100 and compare it with a prime-list on Wikipedia.

[Ashkin]

Yep, I get 17 for prime numbers under 10.
I also generated a list of primes up to 1000 and they all seem to check out (I didn't check thoroughly).

[Dacke]

The data that Jack Sanders provided was for Number. But in the code int is used in the summation code. Perhaps int has a much lower limit?

edit: Yup, that's it.
http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/int.html

MAX_VALUE : int = 2147483647

If you are working with numbers that exceed int.MAX_VALUE, consider using Number.

This is why you should do manual tests!

[Ashkin]

Wait. You're right, I was translating it through int. Works now.
(KILL MEEEEEEEEEEEE AAAAAAAAAAAAAAAAAAAAGH)

[Dacke]

A simple mistake which teaches you a valuable lesson! They create problems that appear trivial but hide little gemstones of Evil inside of them. This is the way Project Euler shows you the limits of your language!

[Mattivc]

Awsome site.
Great way to improve my programming skills.

And my key is, pleas add me to the board as well.
41210212327809_4c72528641cc3ff167a481aadaf3910e