Problem 003

[hk]

I've looked at the Sieve of Eratosthenes, and similar methods, but I don't see the advantage; one would still have to store the primes up the number being factored...

Actually only up to the square root of the number being factored.
Please read the overview/pdf provided by the problem.

[Ocifer]

I've looked at the Sieve of Eratosthenes, and similar methods, but I don't see the advantage; one would still have to store the primes up the number being factored...

Actually only up to the square root of the number being factored.
Please read the overview/pdf provided by the problem.

Where do I find this pdf? Can you please explain why it's efficient to store all the primes up the square root? I understand it's a lesser number and therefore the algorithm will terminate faster, but as the numbers get big the square root will also be rather large. If I do adopt this method, should I allocate an array? If I opt for dynamic memory allocation, there's no guarantee my program will work if there are too many primes for it to store.

[TripleM]

You'll see a PDF icon to the right of the green checkmark (for some solved problems) on the problem listing page: http://projecteuler.net/index.php?section=problems

[Ocifer]

Thanks, TripleM. The PDF helped. A hint to anyone that is experiencing the same confusion I had, you are not actually meant to store the prime numbers generated by the Sieve method; rather, you are meant to use a fact derived from the Sieve of Eratosthenes to improve the bounds of your factoring algorithm.

[anant718]

My code can solve for only small numbers,as the one given as sample in the question.But the console window dosent display anything when i apply the code on the number whose prime factor is required.What do i do?is there some other way to handle large numbers like these?I even used long type.Please help.

[stijn263]

It would help if you told us your programming language. In C++, one of the following should work:
long long A = 600851475143ll;
or
__int64 A = 600851475143ll;

[anant718]

I've recently started working in c# and tried writing the code in it only.

[stijn263]

perhaps Int64 or int64 works? You can check the limits of int64 with something like this:

Int64 p = 10;
Int64 x = 1;

x = x*p;
x = x*p;
x = x*p;
x = x*p;
x = x*p;

etc (I'd suggest writing a loop, but I wouldn't know how to do that in C#)

[anant718]

Thanks a ton...I figured that out myself today....

[wygk123]

}

[hk]

Posting solutions is against forum rules.
Please remove them.
I sent you a warning.

[horance_89]

I have done a c++ little program and i think i got the result!
But woldn´t work inputed..
look at my code a little(the part with getprimefactor isn´t made by me)

Code: Select all

snip

So...i guess it should work fine!
Your opinions?
Edited:
Oks..sry about code posted..but i still do not understand why wouldn´t get my answer!??

[rayfil]

Sorry. Your code got snipped. Maybe you forgot to read the large red letters at the top of the page:
In particular don't post any code fragments or results.

[zlaw777]

My code is working in Java for the number 13195. However, it does not work for the large number simply because Java is saying the number is too large. I tried using long instead of int, this did not help. How do I use large numbers in Java?

[jaap]

My code is working in Java for the number 13195. However, it does not work for the large number simply because Java is saying the number is too large. I tried using long instead of int, this did not help. How do I use large numbers in Java?

Try something like:

Code: Select all

long n = 600851475143L;

Note the L at the end of the number to indicate that it is a long. Without that the literal number is assumed to denote an integer (which is then converted to long for the assignment to n). The literal number (without L) however is not a valid integer so it won't compile.

[swartzism]

I believe I have a correct algorithm to solve this problem, but the number in this problem is making my computer go haywire. If I do a little test to see if gcc on cygwin (windows) can handle the 600851... number, it gives some strange results. Here is my test code: (does not have to do with solving this problem at all! Don't worry!)

Code: Select all

#include <stdio.h>
#include <math.h>

int main()
{
   long long n = 600851475143ll; // have also tried with LL
   long long o = sqrt(n);

   printf("%d\n", n);
   printf("%d\n", o);

   return 0;
}

The results I get are:

-443942297
775146

I believe the resulting number of printing out "n" is why my program is not working. Any ideas why this is what I'm getting?

Thanks in advance.

[jaap]

Try this:

Code: Select all

printf("%lld\n", n);

%d is only for ints, %ld is for longs, and %lld is the most supported format tag for long longs.

[parliament718]

Hi, Ive been trying to do problem #3 for some time now, I've built a program that finds the prime factors of many numbers successfully including 13975 which is included in the problem. However when i try to solve it for the number 600851475143 i get the output: the prime factors for 6.00851 e11 is 2... and thats it... just 2 which is clearly wrong. Can somebody tell me where I'm going wrong. I'm not sure where I could ask for help but I made sure not to put it in the section where there are no spoilers allowed.

Here's the code and thanks in advance.

Code: Select all

#include <iostream>
using namespace std;
#include <iomanip>
using namespace std;
#include <vector>
using namespace std;
#include <math.h>
using namespace std; 


// This program will take a number and find its divisors, then store them in an doubleerger vector.

void findPrimeDivisors(double, double, vector<double> &);
bool isPrime (double);

void main()
{

  double number;
  double vectorindex = 0;
  vector <double> divisors;
  vector <double> primes;
  


  cout << "Please enter the number for which you would like to find the divisors: " << endl;
  cin >> number;
  cout << "The primefactors for " << number <<" are: " ;
  findPrimeDivisors (number, vectorindex, divisors);
  cout<< endl;
  
  cin >> number; //Delay program exit
}

void findPrimeDivisors(double num, double index,  vector<double> &integers)
{
  for(double counter = 1; counter <= num; counter ++)
  {
       
    if ( (int)num % (int)counter == 0) // Checking if 'counter' is a divisor of 'number'
      {
		 if ( isPrime(counter) )       // If it's a divisor, checking if it's prime.
         {
		 integers.push_back(counter);
         cout << integers[index] << " ";
         index ++;   
		 }
      }
	
  }   
}

 bool isPrime (double num)
{

	if (num <=1)
		return false;
	else if (num == 2)         
		return true;
	else if ((int)num % 2 == 0)
		return false;
	else
	{
		bool prime = true;
		double divisor = 3;
		double num_d = static_cast<double>(num);
		double upperLimit = static_cast<double>(sqrt(num_d) +1);
        
		while (divisor <= upperLimit)
		{
			if ((int)num % (int)divisor == 0)
				prime = false;
			divisor +=2;
		}
		return prime;
	}
}

[rayfil]

@parliament718

Spoilers are NOT allowed ANYWHERE on this open forum.

Since your post is related to a specific PE problem, your post has been transfered to the appropriate sub-forum and topic. FYI, problem numbers under #100 are padded with leading 0's to have a standard 3-digit number for ease of listing and searching.

You may even find an answer to your dilemma by reading this topic. If you do find the answer, you should edit your post to remove your code in part or its entirety. Welcome to this open forum.

[GenePeer]

1) 600851475143 isn't even, so how can 2 be a factor?
2) Why are you using double? 6.00851e11 is not equal to 600851475143
3) I don't know how fast your computer is, but I doubt it would finish this loop "for(c=1 ; c<600851475143; c++)" in less than a minute.