Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Spehss _]

Did Project Euler problem 1. At first I thought I'd make a vector containing all the numbers from 1 to the goal number variable, then run through the vector and if the slot was either slot%3==0 or slot%5==0 then I'd add that slot to a variable storing the end sum. Then I changed that to an array. Then I scrapped the array and just made a for loop.

Seems to be right. It gets 23 when made to calculate from 1 to 10.

Spoiler (click to show/hide)

Code: [Select]

//project euler problem 1
/*

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

*/

#include <iostream>

using namespace std;

class nums
{
public:
    int goal=0;
    void getGoal()
    {
        cout<<"Enter a number. The program will find all the multiples of 3 and 5 \nfrom 1 to this number."<<endl;
        cout<<"your number : ";
        cin>>goal;
    }
    void calculate()
    {
        int result=0;
        for(int i=1; i<goal; i++)
        {
            if(i%3==0)
            {
                result+=i;
            }
            else if(i%5==0)
            {
                result+=i;
            }
        }
        cout<<"Result : "<<result<<endl;

    }
};

int main()
{
    nums init;
    init.getGoal();
    init.calculate();
    return 0;
}


I probably could make it faster / more efficient by taking everything in the class and just putting it in main, but eh. Would rather feel like I'm doing some kind of object oriented programming. Or at least attempting to do object oriented programming. :v

Project Euler seems fun. I always liked the little programming assignments I'd have to solve in comp sci classes.

[Orange Wizard]

Spoiler: Problem 1 in Python (click to show/hide)

Code: [Select]

t = 0
for n in range (1000):
    if n % 5 == 0 and n % 3 == 0:
        t += n
print (t)


[Putnam]

Python has the % modulo operator, y'know.

[Orange Wizard]

Shush.

[Spehss _]

Solved Problem 3 on Euler. These are more fun than I think they should be.

Spoiler (click to show/hide)

Code: [Select]

/*
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600,851,475,143 ?
*/

#include <iostream>

using namespace std;

int factor(long long int num)
{
    for(long long int i=1; i<num; i++)
    {
        if(num%i==0&&i!=1)
        {
            cout<<num<<" / "<<i<<" = ";    //debug part 1
            num=num/i;
            cout<<num<<endl;        //debug part 2
            i=1;
        }
    }
    return num;
}

int main()
{
    long long int u_in; //user input num
    do
    {
        cout<<"Enter a number to be factored. Enter 0 to end the program."<<endl;
        if(u_in!=0)
        {
            cin>> u_in;
            cout<<"Initial number   : "<<u_in<<endl;   //debug;
            cout<<"Factor Result    : "<<factor(u_in)<<"\n\n"<<endl;
        }
    }while(u_in!=0);
    return 0;
}


Gets 6857 out of the goal of 600,851,475,143.

[Reelya]

I probably could make it faster / more efficient by taking everything in the class and just putting it in main, but eh. Would rather feel like I'm doing some kind of object oriented programming. Or at least attempting to do object oriented programming. :v

EDIT: OOh yeah I got the Euler#1 solution down to a single line operation you could do on a pocket calculator!

Spoiler (click to show/hide)

you can take a leaf from Gauss and work out a formula instead of a loop.

Find a formula (F) for adding all the numbers that are multiples of a certain number up to 'x'

Then get result F(3) + F(5) - F(15)

for formula F, you can just use the gauss formula for adding all the numbers from 1 to x, then scaling it up to whatever is needed, e.g. adding all multiples of 5 up to below 1000 is the same as adding all integers from 1 to 199, then multiplying the result by 5.

(333(333+1)/2) * 3 + (199(199+1)/2) * 5 - 66(66+1)/2 * 15)
 
EDITED: I missed the condition of "below" and calculated "up to" instead, so I had to knock one off the iterations on the 5's

[miauw62]

Formula for the sum of a row u_n is s_n = n * (u1 +un) / 2, so you just find the highest multiple, calculate it's position in the row, do this for the other number and add them.

FAKEDIT: just realized that you probably can't add a number twice, which makes formulas significantly harder. E2: oh Reelya figured it out, but at least I provided where the formula comes from.

Also @Spessh: check out UVA Online Judge, it has a fuckton of programming problems.

E3: Also Spessh your prime factorization is horribly inefficient ;~; (but I forgot how you're supposed to make a more efficient version)

[Reelya]

For the primes you should make something that spits out all primes <= num/2, then check against that list. No need to check all numbers up to num (but you should check whether num itself is prime).

There are definitely quite a few tricks you can do to generate a list of primes. Even just naive changes can speed up the process quite a bit. First up, other than 2, all primes will be odd. That halves your search space right away. Then you can realize the same things holds for 3, so you can now step up 6 places per loop, and only check the things that are not multiples of 2 or 3. so you check in this pattern:

// pre-check against 2 and 3 and 5 factors here.

for(int i = 6; i<=num/2;i+=6)
{
    // first loop of i checks against 0,1,2,3,4,5. second loop if i checks aganist 6,7,8,9,10,11 etc
    // i+0, i+2, i+4 are invalid (even), as is i+3 (multiple of three)
    // so for each loop, you need to check i+1 amd i+5 only
   
    // so this halves the checks (num/2) then checks only 1/3 remaining values. Total speedup factor = 6
}

You could extend this to also including factors of 5 in the pattern, but then you're skipping 30 places at once so it would be a bit more messy, and there are diminishing returns since you're only ruling out additional factors of i+5, i+25 out of every 30. The other multiples of 5 were already covered by being divisible by 2 or 3. Hence, this particular speed up is only viable up to factors of 3.

[Putnam]

For the primes you should make something that spits out all primes <= num/2, then check against that list. No need to check all numbers up to num (but you should check whether num itself is prime).

You can check up to sqrt(num) instead of num/2 (since you can take num/(number divisible by num) to get the number on the opposite side of the sqrt).

[Reelya]

Actually you could exploit that further by taking into account that you only need to calculate up to the sqrt of the remaining unfactored part, not the sqrt of the original number. e.g. (pseudocode)

Spoiler (click to show/hide)

int num = 143360; // original number to factorize (2^12 * 5 * 7)
int cnum = num; // current num
int f = 2;
while (f <= sqrt (cnum))
{
    while( cnum % f == 0) // while loop to take into account multiples of the same factor
    {
        cnum /= f;
        // add f to list of factors
    }

    f++;
}

This would massively speed things up. Since if e.g. the original number was 2^12 * 5 * 7, then you would clear out the 2^12 on the first iteration, then only proceed up to <= sqrt(35), so would consider factors of 2,3,4,5. Any remaining after the loop ends must be a final prime factor of 7.

[Spehss _]

E3: Also Spessh your prime factorization is horribly inefficient ;~; (but I forgot how you're supposed to make a more efficient version)

It works though. :v

[Reelya]

Well I checked that the snippet of code I provided in the last post works by solving Euler problem #3 with it.

[TheDarkStar]

I've just started the Euler problem archive. Now I have to relearn file I/O because I don't want to enter the gigantic number for Problem 8. 

[Gatleos]

Do you guys know a way to solve a connected components problem that isn't brute force? The brute force method looks like this. Basically, you loop over every single tile, skipping ones that have already been flood-filled and doing a depth-first search otherwise. The grid shown in that example is pretty small, but I'm working with a pseudo-rectangular hex grid of size 128x128. It creates a noticeable frame drop whenever I run it. Not too bad, but I want to improve it if possible.

The tiles are terrain types, all but one of them being land. The flood fill detects contiguous chunks of terrain tiles of the same type, but in addition to this I need to detect water and landmasses separately. A landmass can have many terrain type regions in it. Right now, I'm thinking of saving the coordinate of a single tile in each region, then after I detect all the regions I'll perform an A* pathfinding check between regions to tell if they're in the same landmass. Summing up the sizes of the regions gives me the landmass size.

[MagmaMcFry]

I've just started the Euler problem archive. Now I have to relearn file I/O because I don't want to enter the gigantic number for Problem 8. 

Can't you just copy-paste the string into your code instead of into a separate file?

Do you guys know a way to solve a connected components problem that isn't brute force? The brute force method looks like this. Basically, you loop over every single tile, skipping ones that have already been flood-filled and doing a depth-first search otherwise. The grid shown in that example is pretty small, but I'm working with a pseudo-rectangular hex grid of size 128x128. It creates a noticeable frame drop whenever I run it. Not too bad, but I want to improve it if possible.

The tiles are terrain types, all but one of them being land. The flood fill detects contiguous chunks of terrain tiles of the same type, but in addition to this I need to detect water and landmasses separately. A landmass can have many terrain type regions in it. Right now, I'm thinking of saving the coordinate of a single tile in each region, then after I detect all the regions I'll perform an A* pathfinding check between regions to tell if they're in the same landmass. Summing up the sizes of the regions gives me the landmass size.

Technically, the floodfill algorithm is the fastest possible to detect contiguous tiles. If you're getting frame drops, you're definitely doing something wrong, because floodfill runs in linear time, which should be done in an instant considering how small your grid is.

Could you maybe describe your problem in more detail? Why, when and how often are you doing a floodfill? I need more context please. Also maybe some source. After all, you could be doing something entirely different wrong.