ProjectEuler 3 Quicker way?

[LN7oGNh0]

Im sure someone has posted something a bout this before, but I already have code that works... (at least thats what think.) Heres the code:

#include <iostream>

using namespace std;

double divide(double x, double y)
{
	return x / y;
}

int main()
{	
	double number = 600851475143;
	double i = 3;
	tryagain: //where goto statement goes to
	divide(number, i);
	if (divide(number, i) == 0.0)
	{
		cout << "\nyay";
		cout << "\n" << i;
	}
	else 
	{
		cout << "\nawww.";
		cout << "\n" << divide(number, i);
		i+=2;
		goto tryagain; //increment i by 2
	}
	cin.get();
	return 0;
}

This takes absolutely ages to run! Is there a quicker way? (The program still hasn't finished.)

[Lowest0ne]

Remove lines 23 and 24 and it will go much faster. You need to use modulus though, not division. If you did use division, you need to check that the result is a whole number.

[LN7oGNh0]

thanks. ill try it.
I cant use modulus with doubles so that is why i am using division

[Disch]

but why are you using doubles?

long long number = 600851475143;

// now modulus will work 

Not to mention doubles have floating point rounding errors, so the odds of you getting an exact whole number as the result of division is extremely slim. (ie: 10.0 / 5.0 might actually give you 1.999999999999 instead of 2.0)

[LN7oGNh0]

Ya. Ive tried using long long but when I try it just doesnt work out...

[LN7oGNh0]

heres the new code:

#include <iostream>

using namespace std;

long long modulus(long long x, int y)
{
	return x % y;
}

int main()
{	
	long long number = 600851475143;
	int i = 3;
	tryagain:
	modulus(number, i);
	if (modulus(number, i) == 0)
	{
		cout << "\nyay!" << i;
	}
	else
	{
		i++;
		goto tryagain;
	}
	cin.get();
	return 0;
}

the output is 71. (I doubt that's right.)

[Lowest0ne]

Surely your computer has a calculator which will tell you if 600851475143 is divisible by 71.

I don't know what project 3 is though, took a guess that it has something to do with primes. Is it maybe to find the largest prime number of which the remainder is zero?

Edit: I guess the other reason it doesn't end is because if the number was prime, your loop would never end.

else
{
  i++;
  if (i == number) break;  //  You didn't find a factor less than number,
                           // probably don't care about the number itself
  goto tryagain;  // Obligatory "Don't use gotos, use a for loop"
}

[JLBorges]

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

int main()
{
    // What is the largest prime factor of the number 600851475143 ?
    constexpr std::uint64_t N = 600851475143ULL ;

    const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ;

    // generate a prime number sieve upto the square root of N
    std::vector<bool> sieve( SZ, true ) ;
    for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] )
          for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ;

    // check for divisibility from largest prime number downwards
    std::size_t i = SZ-1 ;
    while( !( sieve[i] && N%i == 0 ) ) --i ;
    std::cout << "largest prime factor of " << N << " is " << i << '\n' ;
}

[Chervil]

@ Hazique35 71 is the smallest prime factor, not the largest. But you could use that information.
Now you can look for prime factors of number/71.

    if (modulus(number, i) == 0)
    {
        cout << "\nyay! " << i;
        number /= i;
        if (number > i)
            goto tryagain;
    }

[LN7oGNh0]

Ya. I pretty much understand what to do now. The only question I have is that Ive tried to use for loops and I always fail with them. How do i do it? I understand them and how to use them but it always ends up badly.

[LN7oGNh0]

Heres an example of me using a for loop:

for (int i = 3; modulus(number, i) == 0; ++i)
{
        modulus(number, i);
	if (modulus(number, i))
	{
		cout << i;
	}
}

The condition is when the remainder is equal to 0. Are functions allowed to be used in the condition? When I run this a blank screen just comes up and then I press enter and exit the program.

Thanks for replying.

[D80DSL3A]

JLBorges +1, Nice.
Very direct.

EDIT: Any reason for switch from size_t to auto from line 15 to 16?
I see it. It ensures that type of j matches type of i.

[LN7oGNh0]

Ya I saw JLBorges as well. Looked very good, but quite hard to understand when you dont understand the code... :)

[D80DSL3A]

If I may dare, I have attempted a translation of JLBorges masterpiece "for the masses" (as the features he used push my envelope as well).

#include <iostream>
using namespace std;

int main()
{
   // What is the largest prime factor of the number 600851475143 ?
    unsigned long long int N = 600851475143ULL ;
    const size_t SZ = 775146;// = floor( sqrt(N) ) as long as we're hardcoding values here

    // generate a prime number sieve upto the square root of N
    bool sieve[SZ] = {0};
    for( size_t i = 2 ; i < SZ ; ++i ) if( !sieve[i] )
            for( size_t j = i*i ; j < SZ ; j += i ) sieve[j] = true ;

    // check for divisibility from largest prime number downwards
    size_t i = SZ-1 ;
    while( sieve[i] || N%i ) --i ;
    cout << "largest prime factor of " << N << " is " << i << '\n' ;
}

Actually, it's an adaptation. I "reversed" the true/false logic so I could avoid explicitly initializing the sieve array elements to true.
It had an interesting effect upon the logic at line 17, which I assume I got correct because the program still gives the correct answer to Euler #3.

EDIT: Spelling correction

[JLBorges]

> EDIT: Any reason for switch from size_t to auto from line 15 to 16?
> I see it. It ensures that type of j matches type of i.

Pedantically, type of j is the promoted type of i.

short i = 7 ;
auto j = i*i ; // type of j is int
decltype(i) k = i*i ; // type of k is short 

[moorecm]

There are some interesting properties of prime numbers that can make solving this problem much faster than testing all numbers. This is a common theme among the Euler problems--to get you to learn something you hadn't realized before. Research prime numbers first, solve the problem second.

[18hRX9L8]

/* Written By: Usandfriends */

#include <iostream>
#include <cmath>

main()
{
      unsigned long n,i,j,usernum;
      bool flag;
      j=0;
      
      std::cout<<"This program finds the greatest prime factor of a number."<<std::endl<<std::endl<<"Enter a number."<<std::endl<<std::endl<<std::endl<<"  > ";
      std::cin>>usernum;
      
      int primes[usernum];
       
       for(n=2;n<usernum;n++)
       {
            flag=true;
            for(i=2;i<=sqrt(n);i++)
            if(n%i==0)
            {
                 flag=false;
                 break;
            }
            if(flag==true)
            {
                 primes[j]=n;
                 j++;
            }
       }
       
       std::cout<<std::endl<<std::endl;
       
       for(n=0;n<j;n++)
       {
            if(usernum%primes[n]==0)
            {
            	while(usernum%primes[n]==0)
            	{
            		usernum=usernum/primes[n];
            	}
            }
            if(usernum==1)
       		{
       			std::cout<<"The greatest prime factor is: "<<primes[n];
       			break;
       		}
       }
       
       if (usernum!=1)
       {
            std::cout<<"The greatest prime factor is: "<<usernum;
       }
}

This doesn't work for big numbers though. Sorry.

[D80DSL3A]

@JLBorges. Thank you.
Line 2 is particularly interesting considering several problems I've recently tackled where I'm intermixing type usage explicitly to avoid overflows on products. These include the allocator (MyMalloc/MyFree) problem you saw, and an 8 digit per node link list class for bigInt, which you may or may not have seen (it passed quickly).

I'll be sure to learn more about that.

@moorecom Good point.

[tntxtnt]

what if 600851475143 is a prime? o.o