Euler Project 3 *For Practice*

[giblit]

Okay I feel like a really big noob I am trying to solve this problem by factoring like this

   100
   /\
  50 2
  /\
 25 2
 /\
5 5

But the problem is I don't even know what the first value that can be factored in is... My code is compiling super slow could anyone possibly help me write up some code that will run much faster. Here is what I have so far ( still waiting on compile could be a VERY long time.

#include <iostream>
#include <vector>

void factorize( unsigned long long &number , std::vector<long long> &factored )
{
    if( number == 1 ) return;
    while( number % 2 == 0 )
    {
        number /= 2;
        factored.emplace_back( 2 );
    }
    for( auto i = 3; i < static_cast<long long>( number / 2 ); i += 2 )
    {
        if( number % i == 0 )
        {
            number /= i;
            factored.emplace_back( i );
            factorize( number , factored );
        }
    }
}

int main()
{
    auto input( 0uLL ) , temp( 0uLL );
    std::vector<long long> factored( 0 );
    std::cout << "Please enter a number\n> " << std::flush;
    std::cin >> input;

    temp = input;
    factorize( temp , factored );
    if( temp > 1 ) factored.emplace_back( temp );
    std::cout << "The factors of " << input << " are:" << std::endl;
    for( const auto &it : factored )
    {
        std::cout << it << std::endl;
    }
    
    std::cout << "The largest prime factor of " << input << " is " << factored.back() << std::endl;
}

I am also using a recursive method to find the prime factors.

Any suggestions would be greatly appreciated =]

[kevinkjt2000]

Any suggestions?
I like solving project euler problems in J.
2 Different solutions to problem 3:

{: q: 600851475143

or

>. / q: 600851475143

http://www.jsoftware.com/

[giblit]

But I am trying to solve in c++ so I can learn c++ better =p and that looks to easy in J

[cire]

You don't need any vectors to solve this problem, and it is a poor candidate for a recursive solution.

On line 12, 3 is of type int. Therefore auto i=3; means that i will be of type int.

[giblit]

Yeah the vector was just for me so I could see what the factors were and whoops I had auto i = 3LL; but I must of accidentally changed it. Thanks for the response is there any way to make it compile faster though or do I just have to wait it out for an answer? I am working on the other problems now since compiling will take a few hours I am guessing.

[Chervil]

Compiling should take a few seconds at most. That's the process of turning the source code into machine language which the computer can understand.

After that you can execute (run) the resulting program. If it takes more than a few seconds it probably means: either you have a very inefficient algorithm or there is an error in the code causing it to get stuck in an infinite loop.

[giblit]

I have a very inefficient algorithm sorry I meant run the program not compile. That's where I was looking for help on improving. Some of these problems are challenging haha I have finished problems 1 2 and 4 so far. 3 is taking too long to compile and 5 I think I did something wrong and need to fix. These problems are pretty fun though and great practice.

*edit*
Ps should I make a new thread for my question on number 5?
----
I am having a difficult time I tried dividing the number by all the primes less than 20( 19 , 17 , 13, 11 , 7 , 5 , 3 & 2 ) then increment but the answer is always just those numbers multiplied which clearly is not the answer.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream> int main() { auto number( 2508uLL ); //closest number to 2520 that is divisible by 19 const unsigned short primes[ 7 ]{ 17 , 13 , 11 , 7 , 5 , 3 , 2 }; //didn't include 19 because it's a given bool divisible( false ); while( !divisible ) { number += 19; //the number must be divisible by the highest prime.. divisible = true; for( const auto &it : primes ) { if( number % it != 0 ) { divisible = false; break; } } } std::cout << number << std::endl; }

9699690 //wrong

Any hints to as what is wrong?

[giblit]

I have come up with a way to find primes so by doing a about 1000 at a time to start then doing about 10k + after that not too much at a time though or it will take forever to compile it took me about 2 minutes to compile the first 100k primes using this:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

void get_prime( std::vector<unsigned long long> &primes )
{
    auto count( 0u );
    auto start( primes.back() );
    auto prime( false );
    while( count < 1000u )
    {
        ++start;
        prime = true;
        for( const auto &it : primes )
        {
            if( start % it == 0 )
            {
                prime = false;
                break;
            }
        }
        if( prime )
        {
            primes.emplace_back( start );
            ++count;
        }
    }
}

int main()
{
    std::ifstream in( "primes.txt" );
    std::vector<unsigned long long> primes( 0 );
    auto temp( 0uLL );
    while( in.good() )
    {
        in >> temp;

        primes.emplace_back( temp );
    }

    get_prime( primes );

    std::sort( primes.begin() , primes.end() );
    primes.resize( std::distance( primes.begin() , std::unique( primes.begin() , primes.end() ) ) );

    std::cout << primes[ 10000 ] << std::endl;

    std::ofstream out( "primes.txt" );

    for( const auto &it : primes )
    {
        out << it << std::endl;
    }
}

I ofstreamed the first 8 primes to start 2 - > 19 and the reason I have the sort/unique is because there is a slight bug where it repeats each time you run and I was too lazy to figure where the bug was. Thanks for all the help.


**Edit
Literally took two seconds to get the answer after I read in the prime numbers from that text file. =]

[naraku9333]

My factoring version http://ideone.com/EH3Xxh

[tntxtnt]

if(u % i == 0)
^
wrong for u = 64 (:

[giblit]

Yeah that works too lol. But my method I can use those primes for problem 10. Might take a very long time for yours.

[tntxtnt]

nah. #10 can be easily solved (run time milisec) with sieve of Eratosthenes

[giblit]

hmm have to google sieve of Erathosthenes..

[giblit]

Oh I see now and I must have really messed up earlier because that was what I was trying to do. I just re-wrote it after looking at wiki and it works similar to tnt's but different code. I don't like to copy and paste. Thanks for the suggestion

[naraku9333]

tntxtnt wrote:

if(u % i == 0)
^
wrong for u = 64 (:

Here ya go. http://ideone.com/y37OhY

[ENIGMAx]

Keep in mind that the runtime of program algorithms is quantifiable, and you can learn about it in most data structures or advanced data structures-like courses or text. I see that in your most recent implementation you dropped the recursive calls of factorize(), which would definitely improve the runtime.

For-loops, and while-loops as well, are very resource intensive, especially for-loops that are nested. Add even one recursive step to that and a calculation gets incredibly more complex. Certain data structures can be much more efficient even with recursion, such as a binary tree, or binomial heap (both with a runtime on the order of log_2(n) or something similar, where n is the number of nodes).

Just my 2 cents before bed, sorry that I can't contribute to a code-related question.

[giblit]

oh it's okay I did that sieve method and it ran in .2 seconds and number 10 in 1.2 seconds which is pretty good I think. Also yeah I am not even in a programming class I am just read up on things in my free time and trying out new things. Trying to finish all those project euler things they are interesting. I haven't really got around to binary trees or binomial heaps or even nodes.