Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411749 Posts in 69684 Topics- by 58650 Members - Latest Member: hans

December 08, 2024, 06:52:51 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)Project Euler
Pages: 1 [2] 3 4
Print
Author Topic: Project Euler  (Read 18895 times)
Ashkin
Guest
« Reply #20 on: April 08, 2012, 01:58:59 PM »

... 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. Facepalm
Anyway, just registered:
17340617327248_4330b9cda8e862e6254c2c02d799836f
I'll probably be terrible at this, but hey, it's worth a try.
Logged
Dacke
Level 10
*****



View Profile
« Reply #21 on: April 08, 2012, 02:06:05 PM »

Hehe, yeah, that's the whole point Durr...?

Quote from: Project Euler
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 Wink)

But anyway, glad to have you aboard! Grin
« Last Edit: April 08, 2012, 02:12:40 PM by Dacke » Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
imaginationac
Level 2
**


Makin' games instead of makin' money.


View Profile WWW
« Reply #22 on: April 08, 2012, 03:04:32 PM »

Here's my key:

50667612327256_708fa68d07e1623bed1580aea227b9a0
Logged

Youtube channel | Charger! Dev Log
              
Ashkin
Guest
« Reply #23 on: April 08, 2012, 09:41:20 PM »

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?
Logged
mokesmoe
Level 10
*****



View Profile WWW
« Reply #24 on: April 08, 2012, 11:10:22 PM »

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.
Logged
Ashkin
Guest
« Reply #25 on: April 08, 2012, 11:15:18 PM »

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.)
Logged
Moczan
Guest
« Reply #26 on: April 09, 2012, 12:55:36 AM »

FlashDevelop is just an IDE, you can't hate it for timing out cause that's FlashPlayer's work  Wink Also your code doesn't do anything. You should look up integer factorization to solve this problem.
Logged
Ashkin
Guest
« Reply #27 on: April 09, 2012, 01:29:11 AM »

I already fixed it. On to problem 4 now.
Man, I feel stupid.
Logged
mokesmoe
Level 10
*****



View Profile WWW
« Reply #28 on: April 09, 2012, 01:34:59 AM »

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.
Logged
Toeofdoom
Level 2
**



View Profile WWW
« Reply #29 on: April 09, 2012, 04:01:11 AM »

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.
Logged

Dacke
Level 10
*****



View Profile
« Reply #30 on: April 09, 2012, 06:57:01 AM »

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.
« Last Edit: April 09, 2012, 08:25:50 AM by Dacke » Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
Ashkin
Guest
« Reply #31 on: April 10, 2012, 01:25:57 AM »

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.
Logged
Dacke
Level 10
*****



View Profile
« Reply #32 on: April 10, 2012, 01:36:49 AM »

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)
« Last Edit: April 10, 2012, 01:58:30 AM by Dacke » Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
BlueSweatshirt
Level 10
*****

the void


View Profile WWW
« Reply #33 on: April 10, 2012, 01:38:56 AM »

Or look it up in the documentation.

http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/Number.html#MAX_VALUE
Quote
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.
Logged

Dacke
Level 10
*****



View Profile
« Reply #34 on: April 10, 2012, 01:48:31 AM »

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.
Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
Ashkin
Guest
« Reply #35 on: April 10, 2012, 02:00:19 AM »

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).
Logged
Dacke
Level 10
*****



View Profile
« Reply #36 on: April 10, 2012, 02:12:05 AM »

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

Quote
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! Well, hello there!
Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
Ashkin
Guest
« Reply #37 on: April 10, 2012, 02:22:26 AM »

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



View Profile
« Reply #38 on: April 10, 2012, 02:24:53 AM »

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!
Logged

programming • free software
animal liberation • veganism
anarcho-communism • intersectionality • feminism
Mattivc
Level 0
***

Level 21 Viking Programmer


View Profile WWW
« Reply #39 on: April 10, 2012, 07:45:16 AM »

Awsome site.
Great way to improve my programming skills.

And my key is, pleas add me to the board as well.
41210212327809_4c72528641cc3ff167a481aadaf3910e
Logged
Pages: 1 [2] 3 4
Print
Jump to:  

Theme orange-lt created by panic