The Beginning

[cdf]

while (multiple_3 < 1000) {
int x = multiple_3 % 10;
if (x != 0 && x != 5) {
current_sum += multiple_3;
}
multiple_3 += 3;
}

Its not only about getting the answer, try getting it in the best way, or as best as you can!
The problem can be solved within just this loop, think about it! Its not about memory or cpu usage now, but the more you think the better you become at solving problems, and in the future this stuff does not only save cpu and memory (still not a big problem unless you are working on something huge), but it will also save you time.
Also, for loops that work with these types of stuff, use a for loop.
GL

[G854izwU]

Thanks your right. I'm still working on the condensing. The next problem I solve I will post the code and ask if that was the best way to do it and if it wasn't I will learn from my mistakes.

[Need4Sleep]

Here is where i started: http://thenewboston.org/list.php?cat=16
Extremely helpful guy, easy to understand!

[G854izwU]

Awesome ill be sure to check that out! =D

[G854izwU]

Hey guys i have been working on problem 3 on Project Euler for 3 hours now and I'm getting confused! The problem is I need to create a program to tell the highest prime factor of 600851475143 So I created the program below and it works great with smaller numbers but it won't show up anything on this one? Can anyone help! Thanks

#include <iostream>

using namespace std;
int checkPrime (int);

int main ()
{

    int number = 600851475143;
    int number_2 = number / 2;

    for (int i = 1; i < number_2; i++) {
        if (number % i == 0){
            int check1 = i;
            int check2 = number / i;
                checkPrime(check1);

                checkPrime(check2);

        }
    }
//cout << i << ", " << number / i << endl;
    return 0;
}

int checkPrime (int numberToCheck) {
    bool prime = true;
    int possibleFactor = 2;
    while (prime == true && possibleFactor < numberToCheck / 2) {

        if (numberToCheck % possibleFactor != 0) {

            prime = true;
            possibleFactor++;

        }
        else {

            prime = false;

        }

    }
    if (prime == true) {
        cout << numberToCheck << " Is a prime number." << endl;
    }
    prime = true;

}

-TheNewKid-

[cire]

Turn up the warnings on your compiler or pay attention to them if they're already on.

VC++:

1>main.cpp(9): warning C4305: 'initializing' : truncation from '__int64' to 'int'
1>main.cpp(9): warning C4309: 'initializing' : truncation of constant value
1> Generating code
1>main.cpp(49): error C4716: 'checkPrime' : must return a value

mingw:

C:\Projects\junk\main.cpp: In function 'int main()':
C:\Projects\junk\main.cpp:9:18: warning: overflow in implicit constant conversion [-Woverflow]
C:\Projects\junk\main.cpp: In function 'int checkPrime(int)':
C:\Projects\junk\main.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]

int isn't large enough to do what you want.

Try long long. And maybe use unsigned to double the range of positive values it can hold.

[G854izwU]

Thanks I changed it to long long and it worked great!

-TheNewKid-

[Fumbles]

I had a go at this myself:

/*

Calculates the highest prime factor of 600,851,475,143.

*/

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

int main(){

	unsigned long long int a=600851475143;
	int t, p = 2, i,k;
	bool b = 0;

	cout << a << '\n';

	for(i=4; i<=pow(a, 0.5);i++){ 	b = 0;
					t = a%i;
						
					if(t == 0){for(k=2; k < pow(i, 0.5);k++){ 	if(i%k == 0) break;
										if(i%k) b = 1;
										}
							}
						
					if(b == 1) p = i;	

				}

	cout << p <<'\n';

return 0;

} 
						

This forum certainly contains some interesting projects!

I got this as an output:

name@computer ~/C++ $ ./bignum
600851475143
486847

Is this what you got? I was writing this quickly.

However, when I compile it I get an error:

name@computer ~/C++ $ g++ bignum.cpp -o bignum -Wall
bignum.cpp:13: warning: integer constant is too large for ‘long’ type

Surely it isn't too large for the long type since it outputs the starting number that I wanted.

P.S: I also cheated on this one. Since I had a feeling the result would be a large prime I decided to skip dividing it by 2 and 3. This made it easier when thinking about the powers.

Also, I used this fact: n is prime if it is indivisible by all k in [2, square root(k)]. This cut down on the number of steps I needed to do.

[DexterMorgan]

http://www.projecteuler.net

Arent the problems there mainly algorithmic, and dont use OOP or template programming?

[DexterMorgan]

For the prime problem, it would be better to count down from the largest possible factor.

Fumbles: you cant assume that the largest prime factor will be less than sqrt(num). Consider 39; the largest prime factor is 13 and 13 > sqrt(39).

Some further optimizations can be used to reduce the number of calls to prime, for these optimizations, think about how you would go about generating a list of primes. The prime cannot be a multiple of 2, 3, or 5 etc.

[cire]

Dexter, factors come in pairs.

If you start from the low end, you find 13 is paired with 3... and there's not any reason to check further.

[DexterMorgan]

cire: DOH!!!!!!!!!!!!!

[DexterMorgan]

Fumbles wrote:

486847....Is this what you got?

Isnt 71 a factor of that?

cire: The pairing property is nice but still one needs to make sure the largest factors are checked.

I was first checking all the factors till num/7 but that program wasnt terminating. Then I thought about the pairing property and realised only 2*sqrt(num) possible factors need to be checked, so I had an upcounting loop and a downcounting loop.

The answer I got had 4 digits, with the first two digits being 68.

I also only check the odd numbers for being possible factors, it cuts down the number of operations by half.

The code is here http://ideone.com/gOj36

ideone is giving a compilation error but on my g++ version (4.4.5) it runs fine with no warnings.

EDIT: http://stackoverflow.com/questions/1458923/long-long-in-c-c
explains the ideone error.

[cire]

Can I ask what made you try:

 const unsigned long long  MAX = a/7-1;
  // MAX needs to be odd. MAX is the largest possible prime factor 

If a = 49, then MAX = 6.

for(i=7; i <sqrta; i= i+2){
    if((a%i == 0) && is_prime(a/i)){
      found = true;
      cout <<"The largest prime factor of " <<a <<" is " <<a/i <<endl;
      return 0;
    }
  }
 
  for(i= sqrta_madeodd; i >=7; i= i-2){
    if((a%i == 0) && is_prime(i)){
      found = true;
      cout <<"The largest prime factor of " <<a <<" is " <<i <<endl;
      return 0;
    }
  }

You can combine these loops -- factors come in pairs.

unsigned long long largest_prime=0 ;

for ( i=7 ; i < sqrta ; i+=2 )
{
     if (  a%i  )
          continue ;

     auto paired_factor = a/i ;
     if ( is_prime(paired_factor) )
     {
          largest_prime = paired_factor ;
          break ;   // there can't be a larger prime factor, so end the loop.
     }

     if ( is_prime(i) )
          largest_prime = i ;
}

 cout <<"The largest prime factor of " <<a <<" is " << largest_prime <<endl;

[DexterMorgan]

Can I ask what made you try:

 const unsigned long long  MAX = a/7-1;
  // MAX needs to be odd. MAX is the largest possible prime factor  

If a = 49, then MAX = 6.

Something dumb.

For the given value of a=600851475143
2,3,4,5,6 can all be ruled out as factors easily by manual inspection. 7 is the least possible factor.
And then I checked that a/7 (int div) is even!

I put in the 7 & MAX thing before I was interating over only sqrt(a) values (you can see that I dont use MAX in my current program).

To make the program more robust, I should iterate starting from 3. That way I only need one assumption for the program, that is, "a" should be odd.


Thanks for the loop combining!
I didnt think of that!

BTW is a%i an expensive operation? Or is there an assembly instruction for division (for long long)?

[DexterMorgan]

You can combine these loops.

I thought about this and I'm not sure loop combining would always be better.

Let N= sqrt(a).

if the largest prime factor is bigger then N, then the two loops approach does better since combining the loops approach leads to more calls to is_prime(); and is_prime() is a costly function.

If the largest prime is less then N, then again is_prime() is called less often in the two loops approach. BUT a%i is called more. Assuming a%i is a cheap operation, the added work is at most O(N).
But the saved work can be much more as is_prime() is a costly function.

[Fumbles]

Hello,

I know that this topic is a bit old, but I decided to give it a go again after my earlier "fumble".

I decided to use a factor tree method (one of the many tidbits of information that I managed to remember from school) and wrote this:

/*

Calculates the highest prime factor of int number types.

*/

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

bool checkprime(int k);
int lpd( int a);

int main() { int a;

	cout << "Calculates the largest prime that divides a number.\n";
	cout << "Enter a number: ";
	cin >> a;

	while(!(checkprime(a))) { a = a / lpd(a); }

	cout << a << '\n';

return 0;

}

//Outputs 1 if k is prime, 0 if it is not prime.
bool checkprime(int k){ bool b = 1;
			
			if(k == 2) return 1;
			for(int i=2; i <= pow(k, 0.5); i++){ if(!(k%i)) b=0; }

return b;	}

//Outputs the lowest prime number that divides a (lowest prime divisor).
int lpd(int a){ for(int i=2;i <= a / 2;i++){ 	if(!(a%i) && checkprime(i)) return i; }
						return a;
		}

It works like this:
1). Takes the number you enter (say a).
2). Finds the lowest prime that divides this number (say p).
3). Lets a = a/p.
4). Goes back to step 1, or terminates if a is prime.
5). Outputs this new prime a.

It seems to work with small numbers:

Calculates the largest prime that divides a number.
Enter a number: 8935
1787

However, it doesn't work for the large number that started this thread!

If I change the int in the function lpd, and the int in the main function (to unsigned long long int) I get an error message:

/tmp/ccIub14M.o: In function `main':
bignum1.cpp:(.text+0x61): undefined reference to `lpd(unsigned long long)'
collect2: ld returned 1 exit status

Is there any way to pass an unsigned long long int into this program?

(P.S: It would be finally nice for me to solve this question once and for all!).

[cire]

The error message suggests you didn't also change the implementation of lpd to match your changed declaration/prototype.

[Fumbles]

Thanks very much. I figured out that there were quite a few places where I needed to redefine the variables to "unsigned long long int".

This is the final result:

/*

Calculates the highest prime factor of 600,851,475,143.

*/

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

bool checkprime(unsigned long long int k);
int lpd(unsigned long long int a);

int main() {unsigned long long int a;

	cout << "Calculates the largest prime that divides a number.\n";
	cout << "Enter a number: ";
	cin >> a;

	while(!(checkprime(a))) { a = a / lpd(a); }

	cout << a << '\n';

return 0;

}

//Outputs 1 if k is prime, 0 if it is not prime.
bool checkprime(unsigned long long int k){ bool b = 1;
			
			if(k == 2) return 1;
			for(int i=2; i <= pow(k, 0.5); i++){ if(!(k%i)) b=0; }

return b;	}

//Outputs the lowest prime number that divides a (lowest prime divisor).
int lpd(unsigned long long int a){ for(int i=2;i <= a / 2;i++){ if(!(a%i) && checkprime(i)) return i; }
						return a;
		} 

..which gives an answer of:

Calculates the largest prime that divides a number.
Enter a number: 600851475143
6857

It was pretty quick too!