eular problem 3

[Blazinteen]

Trying to do the eular problem 3 but my program gives me the initial value of the variable solution for some reason,when it's not even a factor. Would appreciate some help!

#include<iostream>


using namespace std;

int main(){

 long long constant=600851475143;

 long long solution=constant/2;int i=1;int flag=0;int j;

 while(i==1)
 {
 	if(constant%solution==0)                          //checking if its a factor
 	{
 		for(j=2;j<solution;j++)
 		{
 			if(solution%j==0)                      //to check if prime or not
 			{
 				flag=1;
 				
 				break;
			 }
		 }
	 }
      if(flag==0)
	 {
	 	cout<<"the largest prime factor of that shitty number is : "<<solution;
	 	
	 	i=0;
	 }
	 solution--;
 }


}

[Handy Andy]

Hello Blazinteen,

On line 10 You define s"solution" and initialize to to 1/2 of "constant". After that you never change the value of "solution before you print it out on line 28.

I will have to finish up after dinner.

Hope that helps,

Andy

[Handy Andy]

Hello Blazinteen,

I have been working on your program for awhile and have been having a hard time with it.

Line 14. Is the wrong approach and because of it line 16 is never reached.

At line 26. Since "flag" was initialized to zero line 28 is reached well before it needs to and "i" is set to zero causing the while loop to end to soon. And of course the "cout" statement is printing out the wrong variable giving you the wrong answer.

Going back to line 14 you need to know what the answer is to understand the if condition and why it is not working. I added a "cout" statement before the if statement just to see what "constant % solution" was to understand the if condition.

I would loose the if statement on line 14 and keep the for loop. The for loop might be made to work. With what I learned tonight I set up the for loop as: for (c = 3; c < constant / 2; c += 2). This is an old program for me and I am not sure why I used "c" instead of a better name. At the time it worked, but it would be nice if "c" has a better name.

When I did this problem I created a function that returns an "int", but you could just as easily return a bool. All the function does is check for a prime number. The return value is either zero or one, that is why it could be a bool.

Should the functions return value be 1 or true I set what I called "largestPrime" equal to the loop counter, printed out the number, set "pFactor", just a total of all the prime factors done as pFactor *= c and lastly
if (pFactor == num) break; to leave the for loop followed by printing the variable "largestPrime".

As a hint I came up with four prime factors and the largest is above 5000.

Hope that helps,

Andy

[Ganado]

Just a quick note: In general, and especially in Project Euler, always try a simpler version of the actual problem first. Instead of that 600 billion number, try something smaller, like 6 == 3 * 2, and correct your logic from there.

Also, personally, I prefer doing Project Euler in Python because having to worry about int vs long vs BigInteger classes is tangential to the actual learning experience and mathematics from the problems. But that's just my opinion, I'm sure others find making their own BigInteger class to be rewarding.

Also, I could imagine some insane meta-programming that could go into some Euler problems.

[TheIdeasMan]

Further to what the others have said:

With project Euler, brute force is not the right way to do the problems, there is always a way to reduce the size of the data set, or there is some formula to calc the answer, even for the very first problem. You may want to consider revisiting the first problem, now that I have pointed this out :+)

As Ganado says start with a smaller example, perhaps the one given in the question.

IIRC the heart of the code for this is only a few lines.

Some other points:

If want to use a constant value, then make use of the const or constexpr keywords.

For large unsigned numbers consider the type std::size_t , this can hold the largest unsigned value the system has.

Good Luck !!

[Blazinteen]

Oh my god how could i have not seen that!

Thanks for lookig into it and showing the path to the solution. Also I'll keep that efficiency thing in mind from now on.

[icy1]

perhaps check the spelling of the famous mathematician's name, too ;D

[icy1]

@TheIdeasMan - these things are usually still brute force, just with early exits and sometimes careful incrementing/decrementing. For old time's sake, I just wrote a working C++ implementation for this problem, eliminating some checks, but I'm not going to sit there and proof it with Pencil&Paper for half an hour just to eliminate a few thousand more.

Depends on the problem and the language of course. If it's not finishing in seconds, then it's usually a sign that there can be some improvement. I remember doing a bunch of these in Ruby 1.8, which was already slow af due to lang limitations. Huge performance boosts came about in the 1.9.x and 2.x.x releases.

[TheIdeasMan]

@icy1

By brute force I mean not testing every value, or not finding ways to reduce the data set a lot. If one tests each value up to n/2, I still consider that brute force. The main purpose of Project Euler and similar sites is to find clever ways to do the problems efficiently. Some sites have cpu time limits of only 1 second, and some of the problems including this one can complete execution in milliseconds using C++.

If all the problems could be solved with brute force, then probably no one would learn anything. The introduction to a Algorithms & Data Structures course usually has examples of poor algorithms that would take decades or even centuries of computing time, while a good algorithm could solve the same problem in less than 1 second.

[lastchance]

#include <iostream>
#include <cmath>
using namespace std;

using INT = unsigned long long;

int main()
{
   INT N = 600851475143;               // number to be factorised
   INT MAX = sqrt( N + 1.0 );          // limit of search for a proper factor (+ 1.0 for safety)
   INT i = 2;                          // trial factor
   INT last;                           // largest prime factor

   while ( i <= MAX )
   {
      if ( N % i == 0 )                // test for factor
      {
         cout << i << " ";
         last = i;
         N /= i;                       // adjust for remainder, so as to reduce number
         MAX = sqrt( N + 1.0 );        // adjust search maximum
      }
      else
      {
         i = i + 1 + ( i > 2 );        // from 2 to 3, or from odd number to next odd number
      }
   }

   if ( N != 1 ) 
   {
      cout << N << " ";                // remaining factor (if any)
      last = N;
   }

   cout << "\nHighest prime factor is " << last;
}

[icy1]

really nice. I just had the Sieve and was counting backwards by 2's and 4's, checking against it.

Edit: nvm, lol, removed for now. Found a bunch of bugs where the end of my Sieve was less than the possible greatest factor. #feelsbadman

Edit2: fixed; without Sieve or sqrt, counting upwards by 2's and 4's this time.

Edit3: fine, you need the sqrt for large prime inputs =S

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long LargestPrimeFactor(long n)
{
    long rem = 1;
    long prime_factor = 1;
    int simples[] = {2, 3, 5};
    for (int& i : simples)
    {
        while (n%i == 0)
        {
            prime_factor = i;
            rem = n/=i;
        }
    }
    
    // Toggles incrementing by 4 or 2
    bool toggle = true;
    long search = sqrt(n);
    for (long i=7; i<=search; i+=2)
    {
        while (n%i == 0)
        {
            prime_factor = i;
            rem = n/=i;
            search = sqrt(n);
        }
        if (toggle)
            i+=2;
        toggle = !toggle;
    }
    
    return (rem==1 && prime_factor==1) ? n : max(rem, prime_factor);
}

//The prime factors of 13195 are 5, 7, 13 and 29.
//what is the largest prime factor of the number 600851475143 ?
int main() 
{
    vector<long> examples =
    {
        100,
        326,
        1693,  // Prime
        2282,
        13195, 
        13197,
        13199,
        13201,
        13203,
        13207,
        13209,
        13211,
        13213,
        13217,  // Prime
        600851475143,
        999998727899999 // Prime
    };
    
    for (auto& e: examples)
    {
        cout << e << ": " << LargestPrimeFactor(e) << endl;
    }
}

https://repl.it/repls/BrownGlaringMapping

100: 5
326: 163
1693: 1693
2282: 163
13195: 29
13197: 83
13199: 197
13201: 307
13203: 163
13207: 281
13209: 37
13211: 1201
13213: 181
13217: 13217
600851475143: 6857
999998727899999: 999998727899999

[tpb]

Simple solution. Runs instantaneously (at least on the given input :-) ).

#include <iostream>
int main() {
    long long n = 600851475143, i = 3;
    for ( ; n > 1; i += 2)
        while (n % i == 0)
            n /= i;
    std::cout << i - 2 << '\n';
}

[lastchance]

Try it with
999998727899999

https://primes.utm.edu/

[tpb]

No thanks! :-) I said it worked for the given input, which is all the problem requires.

[icy1]

@lastchance, Fine, I put the sqrt back in! It totally doesn't look like your solution now *hides*

[lastchance]

The square root reduces the search range for the smallest factor considerably.
N = 10 000 000 000
N / 2 = 5 000 000 000
sqrt(N) = 100 000
That's a 50000 times difference in the number of checks

If there are any relatively small factors then the number tumbles quickly (as in Euler 3), so it doesn't really matter. However, for checking large primes it makes a huge difference.

Well, didn't this thread give us a lot of fun!!!