Thread: Help!! Problem 3 of Project Euler

Hi,
I started Project Euler sometimes ago and I have managed to finish problem 1 and 2 but now I am stuck on problem 3.As it says, I have implemented the code for 13195 but it doesn't work for 600851475143.

Code:

#include <stdio.h>
#include <stdlib.h>


int main(void){
    
     int i;
     int j=0;
     int k=2;
     int n=0;
     int number=13196;
     int factor[100];
     int prime[100];
     int isNotPrime;
     int largestPrime;
     
    for(i=1;i<number;i++){
        
        if((number-1)%i==0){
            
            //Factor is stored in the factor array
            factor[j]=i;
            
            
            
            for(k=2;k<(factor[j]);k++){
                
                //if the remainder of jth factor and kth number is 0
                if(factor[j]%k==0){
                    
                    //isNotPrime stores jth factor
                    isNotPrime=factor[j];
                    
                }
            }
            
            //If jth factor is not 1 and jth factor is not stored as isNotPrime
            if(factor[j]!=1 && isNotPrime!=factor[j]){
                
                //prime stores jth factor at nth location
                prime[n]=factor[j];
                
                
                //if nth prime is bigger than prime at first postion
                if(prime[n]>prime[0]){
                    
                    //maxPrime stores nth prime
                    largestPrime=prime[n];
                
                    
                }else{
                    
                    //prime at first position is largest prime
                    largestPrime=prime[0];
                    
                }
                n++;
            }
            
            j++;
            
            
        }
        
        
    } 
        //Print results
         printf("The largest prime factor of 13195 is ");
        printf("%d\n",largestPrime);
    
return EXIT_SUCCESS;    
}

This doesn't work!!!

It doesn't display anything

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>


int main(void){
    
      uint64_t  i;
      uint64_t  j=0;
      uint64_t  k=2;
      uint64_t  n=0;
      uint64_t  number=600851475144;
      uint64_t  factor[100];
      uint64_t  prime[100];
      uint64_t  isNotPrime;
      uint64_t  largestPrime;
     
    for(i=1;i<number;i++){
        
        if((number-1)%i==0){
            
            //Factor is stored in the factor array
            factor[j]=i;
            
            
            
            for(k=2;k<(factor[j]);k++){
                
                //if the remainder of jth factor and kth number is 0
                if(factor[j]%k==0){
                    
                    //isNotPrime stores jth factor
                    isNotPrime=factor[j];
                    
                }
            }
            
            //If jth factor is not 1 and jth factor is not stored as isNotPrime
            if(factor[j]!=1 && isNotPrime!=factor[j]){
                
                //prime stores jth factor at nth location
                prime[n]=factor[j];
                
                
                //if nth prime is bigger than prime at first postion
                if(prime[n]>prime[0]){
                    
                    //maxPrime stores nth prime
                    largestPrime=prime[n];
                
                    
                }else{
                    
                    //prime at first position is largest prime
                    largestPrime=prime[0];
                    
                }
                n++;
            }
            
            j++;
            
            
        }
        
        
    } 
        //Print results
         printf("The largest prime factor of 600851475143 is ");
        printf("%PRIu64 \n",largestPrime);
    
return EXIT_SUCCESS;    
}

Are you sure you are patient enough?

Try add

Code:

printf("Factor[%llu]=%llu\n",j,i);

on line 24 to not wait in the dark

I guess what people are neglecting to tell you is if you pick a really slow method it can take literally 100 years. If you want a speedy solution you need to think about fast ways to factor big numbers. The GIMPs don't use naive division to find primes and neither should you. Try using a sieve as part of your solution.

Also, mathematically speaking, it is impossible for a prime factor of a composite number to be greater than the square root of the number.