Project Euler problem 3

This is a discussion on Project Euler problem 3 within the C Programming forums, part of the General Programming Boards category; What is the largest prime factor of the number 600851475143 ? My attempt: Code: #include <stdafx.h> int main() { int ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    2

    Project Euler problem 3

    What is the largest prime factor of the number 600851475143 ?

    My attempt:
    Code:
    #include <stdafx.h>
    
    int main() 
    {
    	int num1, num2, num3, num4, lrgprime, sum;
    	lrgprime=num2=num4=sum=0;
    	for (num1=2; num1<300425737572; num1++) {
    		num2=600851475143%num1; 
    
    		if (num2==0) {
    			for (num3=2; num3<=num1; num3++) {
    				num4=num1%num3;
    				if (num4==0 && num1==num3 && num1>=lrgprime)
    					lrgprime=num1; 
    			}		
    		}	
    	}
    	printf("This is the largest prime factor: %d", lrgprime);
    	return 0;
    }
    The machine is just not running this code

    What did I do wrong?

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    The machine is just not running this code
    Not very descriptive.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by SELFMADE View Post
    What is the largest prime factor of the number 600851475143 ?

    My attempt:
    Code:
    #include <stdafx.h>
    
    int main() 
    {
    	int num1, num2, num3, num4, lrgprime, sum;
    	lrgprime=num2=num4=sum=0;	for (num1=2; num1<300425737572; num1++) {
    		num2=600851475143%num1; 
    
    		if (num2==0) {
    			for (num3=2; num3<=num1; num3++) {
    				num4=num1%num3;
    				if (num4==0 && num1==num3 && num1>=lrgprime)
    					lrgprime=num1; 
    			}		
    		}	
    	}
    	printf("This is the largest prime factor: %d", lrgprime);
    	return 0;
    }
    The machine is just not running this code

    What did I do wrong?
    What's that? int, float char, double, long double.........................
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by SELFMADE View Post
    What is the largest prime factor of the number 600851475143 ?
    You need a long int ("%li").
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Aug 2009
    Posts
    2
    I've been trying to solve this problem for the last 3 days without success can someone help me?

    All I need is a function that checks whether a parameter is a prime or not.

  6. #6
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by SELFMADE View Post
    I've been trying to solve this problem for the last 3 days without success can someone help me?

    All I need is a function that checks whether a parameter is a prime or not.
    A prime number is one that is divisible by 1 and itself only. So, you just run a loop starting from 2 till the number and check if it leaves any remainder while dividing with numbers in between. If it leaves a remainder, you need to continue, if the remainder is zero it's not a prime number.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  7. #7
    Registered User
    Join Date
    Sep 2009
    Posts
    1
    Quote Originally Posted by SELFMADE View Post
    What is the largest prime factor of the number 600851475143 ?

    My attempt:
    Code:
    #include <stdafx.h>
    
    int main() 
    {
    	int num1, num2, num3, num4, lrgprime, sum;
    	lrgprime=num2=num4=sum=0;
    	for (num1=2; num1<300425737572; num1++) {
    		num2=600851475143%num1; 
    
    		if (num2==0) {
    			for (num3=2; num3<=num1; num3++) {
    				num4=num1%num3;
    				if (num4==0 && num1==num3 && num1>=lrgprime)
    					lrgprime=num1; 
    			}		
    		}	
    	}
    	printf("This is the largest prime factor: %d", lrgprime);
    	return 0;
    }
    The machine is just not running this code

    What did I do wrong?
    Hello,
    first of all, integers are usually 32 bit long, i.e. you are limited to numbers between 0 an ~4.000.000.000 for unsigned integers.
    For Euler problem #3 you need integers of 64 bit length.
    Try to declare these numbers using one of these types:

    long long n = 600851475143LL, i, prime;
    or
    int64_t n = 600851475143LL, i, prime;
    or
    __int64 n = 600851475143LL, i, prime;

    Important is to add 'LL' at the end of the large numbers to tell the compiler to interprete this as an integer of 64 bit. (This is what I just learned and helped me to solve Euler #3).

    Hope that helps.
    A.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I suggest you start with smaller values. Your program says the largest prime factor of 200 is 50.

    It also looks like the complexity of the algorithm is too bad - you find all factors, and then you attempt to run a primality test on each of those? Just so you know, there must be better ways.

    However I don't think this is where better solutions should be discussed. The point of a challenge is that you do it yourself.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 06:20 AM
  2. Project details: Dedicated
    By Stack Overflow in forum Projects and Job Recruitment
    Replies: 9
    Last Post: 02-22-2005, 03:10 PM
  3. Operating System Project
    By Pete in forum Projects and Job Recruitment
    Replies: 1
    Last Post: 07-15-2004, 10:33 AM
  4. Another question on classes
    By hpy_gilmore8 in forum C++ Programming
    Replies: 26
    Last Post: 05-24-2003, 10:11 AM

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